53. Maximum Subarray

Kadane’s algorithm looks like magic the first time you see it — three lines, one pass, done. It stops being magic once you see it as a single decision repeated at every index: keep extending the current run, or throw it away and start fresh here.

Question

Given an integer array nums, find the subarray with the largest sum, and return its sum.

• Example1

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

• Example2

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

• Example3

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

• Constraints
  • $1 <= nums.length <= 10^5$
  • $-10^4 <= nums[i] <= 10^4$
• Follow up:
  • If you have figured out the $O(n)$ solution, try coding another solution using the divide and conquer approach, which is more subtle.

Answer 1: Dynamic programming

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

public int maxSubArray(int[] nums) {

    int max = nums[0];

    int[] sum = new int[nums.length];
    sum[0] = nums[0];

    for (int i = 1; i < nums.length; i++) {
        sum[i] = Math.max(nums[i], sum[i - 1] + nums[i]);
        max    = Math.max(max, sum[i]);
    }
    return max;
}

Here sum[i] means “the largest subarray sum that ends exactly at index i.” That framing is the key: a subarray ending at i is either just nums[i] on its own, or nums[i] glued onto the best run ending at i - 1. Whichever is bigger wins — that’s the Math.max(nums[i], sum[i - 1] + nums[i]). The moment sum[i - 1] goes negative, dragging it forward can only hurt, so the algorithm restarts.

Answer 2: Kadane’s Algorithm

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

public int maxSubArray(int[] nums) {

    int max = nums[0];
    int sum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        sum = Math.max(sum + nums[i], nums[i]);
        max = Math.max(sum, max);
    }

    return max;
}

Notice sum[i] only ever reads sum[i - 1] — one step back, never the whole table. So the array collapses into a single sum variable and the space drops from $O(n)$ to $O(1)$. This is the same space trick that turns the DP table in Best Time to Buy and Sell Stock into one running value.

Walking through the example

Trace nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. sum is the best run ending here; max is the best seen so far:

i	nums[i]	sum = max(sum+nums[i], nums[i])	max
0	-2	-2	-2
1	1	max(-1, 1) = 1 (restart)	1
2	-3	max(-2, -3) = -2	1
3	4	max(2, 4) = 4 (restart)	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

The two restarts (at i = 1 and i = 3) are the algorithm throwing away a run that had gone negative. The winning subarray [4, -1, 2, 1] is exactly the stretch from the last restart up to the peak at i = 6. For the variant where you multiply instead of add — which breaks this logic because two negatives can flip to a large positive — see Maximum Product Subarray.

References

• https://leetcode.com/problems/maximum-subarray/