一暑始、題目
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [?2,1,?3,4,?1,2,1,?5,4], the contiguous subarray [4,?1,2,1] has the largest sum = 6.
More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
二、解題思路
方案一
典型的DP題：
- 狀態(tài)dp[i]：以A[i]為最后一個(gè)數(shù)的所有max subarray的和兴革。
- 通項(xiàng)公式：dp[i] = dp[i-1]<=0 ? A[i] : dp[i-1]+A[i]
- 由于dp[i]僅取決于dp[i-1]，所以可以僅用一個(gè)變量來(lái)保存前一個(gè)狀態(tài)，而節(jié)省內(nèi)存根穷。
方案二
雖然這道題目用dp解起來(lái)很簡(jiǎn)單，但是題目說(shuō)了导坟，問我們能不能采用divide and conquer的方法解答屿良，也就是二分法。
假設(shè)數(shù)組A[left, right]存在最大區(qū)間惫周，mid = (left + right) / 2尘惧，那么無(wú)非就是三中情況：
- 最大值在A[left, mid - 1]里面
- 最大值在A[mid + 1, right]里面
- 最大值跨過了mid，也就是我們需要計(jì)算[left, mid - 1]區(qū)間的最大值递递，以及[mid + 1, right]的最大值喷橙，然后加上mid，三者之和就是總的最大值
我們可以看到登舞，對(duì)于1和2贰逾，我們通過遞歸可以很方便的求解，然后在同第3的結(jié)果比較菠秒，就是得到的最大值疙剑。
三、解題代碼
方案一
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n]; //dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
}
方案二
public class Solution {
public int maxSubArray(int[] A) {
int maxSum = Integer.MIN_VALUE;
return findMaxSub(A, 0, A.length - 1, maxSum);
}
// recursive to find max sum
// may appear on the left or right part, or across mid(from left to right)
public int findMaxSub(int[] A, int left, int right, int maxSum) {
if(left > right) return Integer.MIN_VALUE;
// get max sub sum from both left and right cases
int mid = (left + right) / 2;
int leftMax = findMaxSub(A, left, mid - 1, maxSum);
int rightMax = findMaxSub(A, mid + 1, right, maxSum);
maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
// get max sum of this range (case: across mid)
// so need to expend to both left and right using mid as center
// mid -> left
int sum = 0, midLeftMax = 0;
for(int i = mid - 1; i >= left; i--) {
sum += A[i];
if(sum > midLeftMax) midLeftMax = sum;
}
// mid -> right
int midRightMax = 0; sum = 0;
for(int i = mid + 1; i <= right; i++) {
sum += A[i];
if(sum > midRightMax) midRightMax = sum;
}
// get the max value from the left, right and across mid
maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
return maxSum;
}
}
下一篇: 6. DP_Maximum product Subarray
上一篇: 4. DP_LeetCode121/122/123 &終極[k]次交易
