YeungYeah 的乱写地

Maximum Sum Circular Subarray

 Posts  

Problem

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray $C[i], C[i+1], ..., C[j]$, there does not exist $i <= k_1, k_2 <= j$ with$k_1 mod A.length = k_2 mod A.length $.)

Examples

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Notes

  1. $-30000 <= A[i] <= 30000$
  2. $1 <= A.length <= 30000$

Solution

暴力法

因为太久没有做过题了，对题目都没什么感觉了，感觉有点熟悉，好像可以用 DP（发现是暑假的时候在紫书中看过），但是一下不知道怎么用。于是先用暴力法试试水。

题目当中要求的是最大子段和，所以考虑枚举所有的子段，每个子段包含一个普通的区间和一个首尾相接的连续区间。 枚举的情况有 $2 * C_n^2$ 种，每种情况计算子段和可以通过累计前缀和来计算，总复杂度为 $O(n^2$)。

最后结果为超时，大概能过 91 / 109 个样例。

最大子序列和算法

暴力法超时后思考无果，上网看看别人的思路。发现求解最大子序列的和有一个很好的算法，就是 Kadane 算法。很好理解，直接在下面提出代码：

1
2
3
4
5
6
7

def kadane(arr):
    if len(arr) == 0: return 0
    ans = cur = arr[0]
    for i in arr[1:]:
        cur = arr[i] + max(cur, 0)
        ans = max(ans, cur)
    return ans

源方法来自于DP的化简，设 $dp[i]$ 为数组以元素 arr[i] 结尾的最大子序列和，则有下列的转移方程。

1

dp[i+1] = dp[i] + arr[i+1] if dp[i] > 0 else arr[i+1]

实际使用过程中无需存储dp数组，为了降低空间复杂度，使用数值变量记录数值即可。

问题进一步分析

于是问题就变成了在求解数组的最大子序列和的基础上，进一步考虑双向区间的和。原本的子序列，只考虑数组的单向区间，这一块可以通过kadane算法求解，所以所需考虑的问题为怎么求双向区间（一头一尾组成）的子数组和。大致有下面三种方法。

相邻数组法

单区间子序列的最大值可以通过Kadane算法直接求出。 环形序列的双区间子序列则可分成左右两部分来找出，我们定义 maxright[i] 为下标为i的元素右侧的最大子序列和，这个可以通过一次倒序扫描求出。所以双区间最大子序列和为 max(leftsums[i] + maxright(i+1) for i in range(N-2))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def fun1(A):
    ans = cur = A[0]
    N = len(A)
    for i in range(1,N):
        cur = A[i] + max(0,cur)
        ans = max(ans,cur)

    leftsums = [A[0] for _ in range(N)]
    for i in range(1,N): leftsums[i] = leftsums[i-1] + A[i]

    rightsums = [A[-1] for _ in range(N)]
    maxright = [A[-1] for _ in range(N)]
    for i in range(N-2,-1,-1):
        rightsums[i] = rightsums[i+1] + A[i]
        maxright[i] = max(maxright[i+1],rightsums[i])

    for i in range(1,N-1):
        ans = max(ans, leftsums[i-1]+maxright[i])

    return ans

变号法

本方法将双区间的序列和转化为整个数组的总和减去单区间子段和，其值为$S - \sum_{k=i}^jA_k$，该值的最大值为后者取最小值时的值，问题变成求解数组元素i到j的最小值，将数组元素全体乘以-1，则变成求解最大值，可套用 kadane 算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def fun2(A):
    def kadane(gen):
        if len(gen) == 0: return 0
        ans = cur = gen[0]
        for i in gen[1:]:
            cur = i + max(cur,0)
            ans = max(ans,cur)
        return ans

    alls = sum(A)
    ans1 = kadane(A)
    ans2 = alls + kadane([-A[i] for i in range(1,len(A)-1)])
    return max(ans1,ans2)

前缀和+优先队列

因为数组A的循环子段必然是数组B=A+A的子段，所以可将数组拼接一次在求单区间的最大子序列和，只需满足子序列长度不超过原数组长度。 对于子序列 B[i+1:j+1]，其和为 P[j]-P[i]，这里我们固定j，找出使 P[i] 最小的 i 值，可通过优先队列实现，这里通过在插入元素时比较当前元素与队列末元素的大小进行插入处理，手动实现优先队列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def fun(A):
    P = A * 2
    for i in range(1,len(P)):
        P[i] = P[i] + P[i-1]

    from collections import deque
    queue = deque([0])
    ans = A[0]
    for j in range(1,len(P)):
        i = queue[0]
        while j - i > len(A):
            queue.popleft()
            i = queue[0]
        ans = max(ans, P[j] - P[i])

        while queue and P[queue[-1]] > P[j]:
            queue.pop()

        queue.append(j)
    return ans

相关文章：