# Maximum Subarray

March 21, 2021

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.

-21-34-121-54
dp-21-2435615
🛎️

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.