一、题目

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题:

  1. 状态dp[i]:以A[i]为最后一个数的所有max subarray的和。
  2. 通项公式:dp[i] = dp[i-1]<=0 ? dp[i] : dp[i-1]+A[i]
  3. 由于dp[i]仅取决于dp[i-1],所以可以仅用一个变量来保存前一个状态,而节省内存。

方案二

虽然这道题目用dp解起来很简单,但是题目说了,问我们能不能采用divide and conquer的方法解答,也就是二分法。

假设数组A[left, right]存在最大区间,mid = (left + right) / 2,那么无非就是三中情况:

  1. 最大值在A[left, mid - 1]里面
  2. 最大值在A[mid + 1, right]里面
  3. 最大值跨过了mid,也就是我们需要计算[left, mid - 1]区间的最大值,以及[mid + 1, right]的最大值,然后加上mid,三者之和就是总的最大值

我们可以看到,对于1和2,我们通过递归可以很方便的求解,然后在同第3的结果比较,就是得到的最大值。

三、解题代码

方案一

  1. public class Solution {
  2. /**
  3. * @param nums: A list of integers
  4. * @return: A integer indicate the sum of max subarray
  5. */
  6. public int maxSubArray(int[] A) {
  7. int n = A.length;
  8. int[] dp = new int[n]; //dp[i] means the maximum subarray ending with A[i];
  9. dp[0] = A[0];
  10. int max = dp[0];
  11. for(int i = 1; i < n; i++){
  12. dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
  13. max = Math.max(max, dp[i]);
  14. }
  15. return max;
  16. }
  17. }

方案二

  1. public class Solution {
  2. public int maxSubArray(int[] A) {
  3. int maxSum = Integer.MIN_VALUE;
  4. return findMaxSub(A, 0, A.length - 1, maxSum);
  5. }
  6. // recursive to find max sum
  7. // may appear on the left or right part, or across mid(from left to right)
  8. public int findMaxSub(int[] A, int left, int right, int maxSum) {
  9. if(left > right) return Integer.MIN_VALUE;
  10. // get max sub sum from both left and right cases
  11. int mid = (left + right) / 2;
  12. int leftMax = findMaxSub(A, left, mid - 1, maxSum);
  13. int rightMax = findMaxSub(A, mid + 1, right, maxSum);
  14. maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
  15. // get max sum of this range (case: across mid)
  16. // so need to expend to both left and right using mid as center
  17. // mid -> left
  18. int sum = 0, midLeftMax = 0;
  19. for(int i = mid - 1; i >= left; i--) {
  20. sum += A[i];
  21. if(sum > midLeftMax) midLeftMax = sum;
  22. }
  23. // mid -> right
  24. int midRightMax = 0; sum = 0;
  25. for(int i = mid + 1; i <= right; i++) {
  26. sum += A[i];
  27. if(sum > midRightMax) midRightMax = sum;
  28. }
  29. // get the max value from the left, right and across mid
  30. maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
  31. return maxSum;
  32. }
  33. }