Define: sum[i] as the maximum subarray sum of [0...i], and this subarray MUST END WITH nums[i].

(Some thought -- when facing "consecutive sequence problems" such as subarray or substring, the subproblems usually MUST END WITH current element, so that when NEXT element comes, the sequence will still remain consecutive).

```
/*Then, from i --> i+1:
-- if sum[i] >= 0, it gives non-negative contribution, sum[i+1] = sum[i] + a[i+1]
-- if sum[i] < 0, it gives negative contribution, sum[i+1] = a[i+1]*/
public class Solution {
public int maxSubArray(int[] nums) {
if (nums==null || nums.length==0) { return 0; }
int max = nums[0], sum = nums[0];
for (int i=1; i<nums.length; ++i) {
if (sum >= 0) { sum += nums[i]; }
else { sum = nums[i]; }
max = Math.max(max, sum);
}
return max;
}
}
```