Maximum Subarray
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 brute-force approach.