算法介绍
对于一个给定数组 A，Kadane 算法可以用来找到 A 的最大子段和。这里，我们只考虑非空子段。Kadane 算法基于动态规划。令 dp[j] 为以 A[j] 结尾的最大子段和。也就是，
那么，以 j+1 j结尾的子段（例如 A[i], A[i+1] + … + A[j+1]）最大化了 A[i] + … + A[j] 的和，当这个子段非空那么就等于 dp[j] 否则就等于 0。所以，有以下递推式：
由于一个子段一定从某个位置截止，所以
就是需要的答案。
为了计算 dp 数组更快，Kadane 算法通常节约空间复杂度的形式表示。我们只维护两个变量 ans 等于
和 cur 等于dp[j]。随着 j 从 0 到 A.length-1遍历。
算法伪码
#Kadane's algorithmans = cur = Nonefor x in A:cur = x + max(cur, 0)ans = max(ans, cur)return ans
应用
力扣918题便是需要使用Kanade算法来进行解答
918. 环形子数组的最大和
给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。 在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，而当 i >= 0 时 C[i+A.length] = C[i]） 此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）> 示例 1：
输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
示例 4：
输入：[3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
示例 5：
输入：[-2,-3,-1]
输出：-1
解释：从子数组 [-1] 得到最大和 -1
提示：
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-sum-circular-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
先贴上我的方法，由于我的方法并不是Kanade方法，所以结果就是在写代码的时候，经常需要根据未通过的case缝缝补补，导致代码十分的臃肿和条理不清晰。
class Solution {
public:
int maxSubarraySumCircular(vector<int>& A) {
int size = A.size();
if(size == 0)
return 0;
if(size == 1)
return A[0];
int ret = INT_MIN;
vector<long>newA;
for(int i = 0; i < size;)
{
long cur = A[i];
if(A[i] < 0)
{
i++;
}
else
{
i++;
while(i < size)
{
if(A[i] >= 0)
cur += A[i];
else
break;
i++;
}
}
newA.push_back(cur);
}
size = newA.size();
if(size == 1)
return newA[0];
for(int i = 0; i < size; i++)
{
int curmax = newA[i];
if(curmax > 0)
{
int end = i;
int start = i;
int sum = newA[i];
start++;
while(start != end)
{
if(start == size)
start = 0;
sum += newA[start];
if(sum > 0)
curmax = max(sum, curmax);
else
break;
start++;
if (start == size)
start = 0;
}
}
ret = max(ret, curmax);
}
return ret;
}
};
在有了上面的基线之后，让我们看看力扣官方给的一些解决方案。我个人一直认为相对于解决力扣的题，其实看别人的解题思路往往对自己的收获更大。不过做到知行合一很难，所以我做出一道题后，往往就懒得看官方题解或是评论了，哈哈哈哈。
方法一：邻接数组
想法和算法
循环数组的子段可以被分成 单区间 子段或者 双区间 子段，取决于定长数组 A 需要多少区间去表示。
例如，如果 A = [0, 1, 2, 3, 4, 5, 6] 是给定的循环数组，我们可以表示子段 [2, 3, 4] 为单区间 [2, 4][2,4]；如果我们希望表示子段 [5, 6, 0, 1]，那就是双区间 [5, 6], [0, 1][5,6],[0,1]。
使用 Kadane 算法，我们知道如何计算一个单区间子段的最大值，所以剩下的问题是双区间子段。
考虑区间为 [0, i], [j, A.length - 1]。计算第i个参数，对于固定 i 两区间子串的最大值。计算 [0, i]的和很简单，考虑，
和
所以期望的第 i个候选结果为：
由于我们可以限行时间计算
和
，结果是显然的。
class Solution(object):
def maxSubarraySumCircular(self, A):
N = len(A)
ans = cur = None
for x in A:
cur = x + max(cur, 0)
ans = max(ans, cur)
rightsums = [None] * N
rightsums[-1] = A[-1]
for i in xrange(N-2, -1, -1):
rightsums[i] = rightsums[i + 1] + A[i];
maxright = [None] * N
maxright[-1] = rightsums[-1]
for i in xrange(N-2, -1, -1):
maxright[i] = max(maxright[i+1], rightsums[i])
leftsum = 0
for i in xrange(N-2):
leftsum += A[i]
ans = max(ans, leftsum + maxright[i+2])
return ans
复杂度分析
- 时间复杂度：O(N)O(N)，其中 NN 是
A的长度。 - 空间复杂度：O(N)O(N)。
方法二：前缀和 + 单调队列
想法
首先，我们可以在一个定长数组上完成这个问题。
们可以认为循环数组 A 的任意子段，一定是定长数组 A+A 的任一个子段。
例如，对于循环数组A = [0,1,2,3,4,5],那么那么它的子段 [4,5,0,1] 一定也是定长数组 [0,1,2,3,4,5,0,1,2,3,4,5] 的子段。令 B = A + A 就是这个定长数组。
假定N = A.length,考虑前缀和
然后，考虑最大的
其中
class Solution(object):
def maxSubarraySumCircular(self, A):
N = len(A)
p = [0]
for _ in xrange(2):
for x in A;
p.append(p[-1] + x)
ans = A[0]
deque = collections.deque([0])
for j in xrange(1, len(p))：
if deque[0] < j - N:
deque.popleft()
ans = max(ans, p[j] - p[deque[0]])
while deque and p[j] <= p[deque[0]]:
deque.pop()
参考资料：
若有收获，就点个赞吧
0 人点赞
