[DP解题] Maximum Sum Circular Subarray 理解 Kadane's algorithm
LeetCode 918. Maximum Sum Circular Subarray
原题链接：https://leetcode.com/problems/maximum-sum-circular-subarray/
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 <= k1, k2 <= j with k1 % A.length = k2 % A.length.)
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
Note:
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
题目大意是：给定由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。）
Kadane's algorithm
可以参考：https://en.wikipedia.org/wiki/Maximum_subarray_problem
Kadane的算法是基于将一组可能的解分解成相互排斥（不相交）的集合。Kadane算法是基于DP的。
假设dp[j] 表示在数组A中以A[j]结束的子数组的最大和，
dp[j] = max(A[i] + A[i+1] + ... + A[j])
那么，以[j+1]结束的子数组（例如：A[i], A[i+1] + ... + A[j+1]）大于 A[i] + ... + A[j] 的和。（A为非空数组，并且元素不为0）
因此：dp[j+1]=A[j+1]+max(dp[j],0)
子数组需要在某处结束，所以，最终的答案就是通过对数组迭代一次来计算以位置j结尾的最大子数组和。
伪代码表示如下：
#Kadane's algorithm
ans = cur = None
for x in A:cur = x + max(cur, 0)ans = max(ans, cur)
return ans算法设计
package com.bean.algorithm.dp;public class MaximumSumCircularSubarray {public static int maxSubarraySumCircular(int[] A) {int minSum = Integer.MAX_VALUE;int maxSum = Integer.MIN_VALUE;int total = 0, sum = 0;for(int i = 0; i < A.length; i++){total += A[i];if( sum + A[i] > A[i] )sum += A[i];elsesum = A[i];maxSum = Math.max(sum, maxSum);}sum = 0;for(int i = 0; i < A.length; i++){if( sum + A[i] < A[i] )sum += A[i];elsesum = A[i];minSum = Math.min(sum, minSum);}return total == minSum ? maxSum : Math.max(maxSum, total - minSum);}public static void main(String[] args) {// TODO Auto-generated method stubint[] demo=new int[] {1,-2,3,-2};int result=maxSubarraySumCircular(demo);System.out.println("result = "+result);}}
运行结果：
result = 3