[DP解題] Maximum Sum Circular Subarray 了解 Kadane's algorithm

[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];
			else
				sum = 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];
			else
				sum = 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 stub
		int[] demo=new int[] {1,-2,3,-2};
		int result=maxSubarraySumCircular(demo);
		System.out.println("result = "+result);
	}

}
           

運作結果：

result = 3