The basic idea is to sum all the way from beginning to the end, if at any time the current sum is negative, reset to zero.

Why?

The concern only happens when we encounter a negative number. Then we have two options.

- Add the negative number into previous sum
- Reset the current sum to zero and start over from the next number

Take a look at the below two examples

**Example 1**

1 2 3 4 -3 5 6

When we encounter -3, previous sum is 10, currentSum will be 7 for option 1 and 0 for option 2.

We would like to add -3 to the current sum and continue.

**Example 2**

1 2 -6 3 4

When we encounter -6, previous sum is 3, currentSum is -3 for option 1 and 0 for option 2.

We would like to start over from the next number 3,

```
public class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int currentSum = 0;
for (int i : nums) {
currentSum += i;
max = Math.max(max, currentSum);
if (currentSum < 0) {
currentSum = 0;
}
}
return max;
}
}
```