- Sweep the initial negative numbers to find a maximum negative number to return in case the array is all nonzero.
- When you get past the initial stream of negative numbers, repeatedly

- add all the consecutive nonnegative numbers. Once finished compare to the max, store if greater than max.
- add all the negative numbers to previous summation. Once it goes below zero, skip the rest of them (no reason to carry them on)

```
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int sum = 0, i = 0;
while (i < nums.length && nums[i] < 0) {
if (nums[i] > max)
max = nums[i];
i++;
}
while ( i < nums.length ) {
for ( ; i < nums.length && nums[i] < 0; i++) {
if (sum > 0)
sum = sum + nums[i];
}
if (sum < 0) sum = 0;
for ( ; i < nums.length && nums[i] >= 0; i++) {
sum = sum + nums[i];
}
if (sum > max) max = sum;
}
return max;
}
```