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.

Analysis:

We define the state d[i] as the the largest sum we can get for subarrays the end at i. We then have the formula:

if d[i-1]<0, then we will choose to just select A[i] at i, d[i]=A[i]; otherwise d[i]=A[i]+d[i-1];

Solution:

 1 public class Solution { 2     public int maxSubArray(int[] A) { 3         int len = A.length; 4         if (len==0) return 0; 5         int[] d = new int[len]; 6         d[0] = A[0]; 7         int max = d[0]; 8         for (int i=1;i<len;i++){ 9             if (d[i-1]<0)10                 d[i]=A[i];11             else 12                 d[i]=A[i]+d[i-1];13             if (d[i]>max) max = d[i];14         }15 16         return max;17     }18 }

Leetcode-Maximum Subarray