53. Maximum Subarray

Problem:

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.

3/29/2018 update:

更新maxEndingHere在sum[0, i - 1] 小于0的情况下，如果当前nums[i] > 0,肯定要把之前的都抛弃。maxEndingHere不一定是包含了0 ~ i所有的数。

相当于维护一个当前的极大和，因为是求subarray，所以最大和肯定是极大和的最大值。

2/23/2018 update
DP solution: maxEndingHere is the max sum from  nums[0] to nums[i] that includes nums[i].

public static int maxSubArray(int[] A) {
    int maxSoFar=A[0], maxEndingHere=A[0];
    for (int i=1;i<A.length;++i){
        maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
        maxSoFar=Math.max(maxSoFar, maxEndingHere); 
    }
    return maxSoFar;
}

10/10/2017

第二种解法用prefix sum的思路来做。

前i个数的maximum subarray = prefixSum[i] - min(prefixSum[0]....prefixSum[i-1])。
在遍历数组的时候需要记录下minSum, sum和max。代码如下

 public class Solution {  
   /*  
    * @param nums: A list of integers  
    * @return: A integer indicate the sum of max subarray  
    */  
   public int maxSubArray(int[] nums) {  
     // write your code here  
     if(nums.length == 0 || nums == null) {  
       return 0;  
     }  
     int max = Integer.MIN_VALUE, sum = 0, minSum = 0;  
     for(int i = 0; i< nums.length ; i++) {  
       sum += nums[i];  
       max = Math.max(max, sum - minSum);  
       minSum = Math.min(sum, minSum);  
     }  
     return max;  
   }  
 }  

--------------------------------------------------------------------------------------------

DP滚动数组问题。

如果sum[i]+nums[i]比nums[i]还小，那么这个时候sum[i]就该取nums[i]，抛弃之前所有的。