Problem 2.4 · ArraysMedium

Maximum Subarray

PatternKadane's Algorithm Running State in One Pass

What it teaches: Kadane's algorithm: the best subarray ending here is either this element alone or it plus the best ending just before.

Practise it on judges as “Maximum Subarray”.

The problem

Given an integer array nums, find the contiguous subarray (at least one element) with the largest sum, and return that sum.

Example 1

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

[4, −1, 2, 1] has the largest sum, 6.

Example 2

Input: nums = [1]
Output: 1

Example 3

Input: nums = [5, 4, -1, 7, 8]
Output: 23

Constraints

1 ≤ nums.length ≤ 10⁵
−10⁴ ≤ nums[i] ≤ 10⁴

Pattern clues in the wording

→ "Contiguous subarray" with the largest sum
→ Negative numbers allowed (a plain sliding window doesn't work)
→ n up to 10⁵ → O(n)

These clues point to Kadane's Algorithm: Scan once, keeping the best sum of a subarray ending here: either extend the previous one or start fresh.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], best = nums[0];
        return best;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [-2,1,-3,4,-1,2,1,-5,4]	6
2	nums = [1]	1
3	nums = [5,4,-1,7,8]	23

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Brute force: every start, growing sum · O(n²)2. Optimal: Kadane's algorithm · O(n)

Brute force: every start, growing sum

Time O(n²) Space O(1)

For each start i, extend the end j one step at a time, keeping a running sum, and track the maximum. Using a running sum avoids an O(n³) re-summing loop.

Approach 1

class Solution {
    public int maxSubArray(int[] nums) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

Verdict: About 5 × 10⁹ steps for n = 10⁵: too slow. The repeated work: every start re-adds the same later elements.

Optimal: Kadane's algorithm

Time O(n) Space O(1)

Let cur be the best sum of a subarray ending at i. Then cur = max(nums[i], cur + nums[i]): extend the previous subarray if it helps, otherwise start fresh. The answer is the largest cur ever seen.

▶ Dry run: Extend or start freshnums = [5, 4, -1, 7, 8]

↑i

-1

State(vars)

cur = 5best = 5

Step 1/5Start: cur = best = 5.

Approach 2

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

Verdict: One pass, two variables. The expected answer.

Before you submit

Edge cases and common mistakes

Test these inputs

All negative → the largest single element
One element
Best subarray is the whole array
Zeros

Mistakes people make

Initialising best to 0.
Resetting cur to 0 when it goes negative but forgetting to handle all-negative arrays (use max(nums[i], cur + nums[i]) instead).

Interview

Follow-up questions

How would you return the start and end indexes too?

What about a circular array, where the subarray can wrap around?

Command Palette