# Maximum Subarray

easy | Accept. 54% | 力扣中文站

Given an integer array `nums`

, find the *contiguous* subarray (containing at least one number) which has the largest sum and return its sum.

Example:

```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```

## Code

```
public int maxSubArray(int[] nums) {
int globalMax = nums[0];
int currentMax = nums[0];
for (int i = 1; i < nums.length; i++) {
currentMax = Math.max(currentMax + nums[i], nums[i]); globalMax = Math.max(globalMax, currentMax);
}
return globalMax;
}
```

## State transition

Try clicking on a cell to see how the value is calculated.

-2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 | |
---|---|---|---|---|---|---|---|---|---|

dp | -2 | 1 | -2 | 4 | 3 | 5 | 6 | 1 | 5 |

🛎️

To understand the state transition function, it’s important to realize that for `dp[i]`

,
we’re only concerned with *contiguous subarrays that end in that position*.
It effectively compares the subarrays in a similar way to the $O(n^2)$ brute-force approach.