53. Maximum Subarray Leetcode Java

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.

Solution:

It is a classic dynamic programming problem.

I use two variables to track two important maximum sum. One is called localMax, which means, it is the max subarray till current index and the current index must be included in this subarray. Another one is called globalMax, which means, it is the max subarray till current index, but there is no requirement of including current index. The invariance is that globalMax will be the maximum of all localMax, because the final Maxmum subarray must be ended in an index which we know that this localMax will be the globalMax. Another thing is that if we have a localMax[i-1], localMax[i]= Math.max(localMax[i-1]+num[i], num[i]) because num[i] must be included in localMax[i]. 

Time complexity: O(n)

  public int maxSubArray(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int localMax=A[0];  
    int globalMax=A[0];  
    for(int i=1;i<A.length;i++){  
      localMax=Math.max(localMax+A[i],A[i]);  
      globalMax=Math.max(localMax,globalMax);  
    }  
    return globalMax;  
   }