What is the brute force approach and complexity for Maximum Subarray?

Add up every subarray from scratch and keep the largest sum with time complexity O(N^3) and space complexity O(1).

What is the optimal approach and complexity for Maximum Subarray?

Track the best run that ends at each index: extend it or restart with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Maximum Subarray?

Look for key signals in the prompt: "contiguous subarray" indicates The answer is a run of neighbours. Think of the best run that ends at each index.; "largest sum" indicates A sum can be updated in O(1): add the new number, or drop the old run and start again.; "at least one number" indicates The answer can be negative, so the start value is a real number, never 0..

Maximum Subarray

Medium·LeetCode #53Basic Anchor

LeetCode

Jump:

30-Second Mental ModelKadane's algorithm (Maximum subarray)

Complexity:O(N^3)→O(N)

Key Insight

Let cur be the largest sum of a run that ends at the current index. At each index, the best run ending here is either this number alone, or this number plus cur, whichever is bigger. Keep best as the largest cur seen so far.

Core Validity Invariant

cur is always the best sum of a subarray that ends exactly at the current index, so it is a valid candidate for the answer at every step.

Problem

You are given an integer array nums. Find a contiguous part of it, a subarray with at least one number, whose sum is as large as possible. Return that largest sum.

A subarray is a run of neighbouring numbers. You cannot skip numbers in the middle.

Input

An integer array nums of length n.

Output

One number: the largest sum of any non-empty subarray.

Example 1

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

Output: 6

The run [4, -1, 2, 1] adds up to 6. No other run of neighbours does better.

Example 2

Input: nums = [1]

Output: 1

The only subarray is [1].

Example 3

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

Output: 23

The whole array is the best run: 5 + 4 − 1 + 7 + 8 = 23.

Constraints

• 1 ≤ nums.length ≤ 10^5
• −10^4 ≤ nums[i] ≤ 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The answer is a run of neighbours. If I know the best run that ends at index 4, how can it help me at index 5?
2.
Can the best run be empty? What is the answer for an array with only one negative number?
3.
If the run so far has a negative sum, is it worth keeping before I add the next number?
4.
Must the best run end at the last index? Where else could it end?
5.
How many runs end at one particular index?

Brute force approach

Idea

Try every pair of positions l ≤ r. For each pair, add up nums[l] … nums[r] with a loop, then keep the biggest total.

Thinking process

1
A subarray is decided by two ends: a start l and an end r.
2
Check [-2, 1, -3]: the pair (0, 0) gives -2, (0, 1) gives -1, (0, 2) gives -4, (1, 1) gives 1, (1, 2) gives -2, and (2, 2) gives -3. The biggest is 1.
3
Each pair is summed from scratch with an inner loop, so the same numbers are added again and again.
4
Keep the largest total seen. Start the answer from a real subarray sum, not from 0, because every sum here can be negative.

Visual

Orange cells were already added on the previous round with the same start, and brute force adds them again. Input: the first five numbers of the dry run.

Brute force re-adds numbersnums = [-2, 1, -3, 4, -1]step 1/16

nums

-2

-3

-1

▲start end

Work

numbers added this round: 1
already added last round: 0
total additions: 1
sum of this run: −2
best: −2

New start: add from scratch

Start 0, end 0: add 1 numbers from scratch, giving −2.

Code & Implementation

brute.cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int best = INT_MIN;

        // Try every subarray nums[l..r].
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                // Re-add the whole run from scratch for this pair.
                int sum = 0;
                for (int i = l; i <= r; i++) {
                    sum += nums[i];
                }
                best = max(best, sum);
            }
        }
        return best;
    }
};

Complexity

Time O(N^3)Space O(1)

Three nested loops: l, r, and the sum from l to r. For n = 10^5 that is about n³/6 ≈ 1.7 · 10^14 additions.

Better approach

Why brute force is slow

Every pair (l, r) is summed from scratch, so the same numbers are added again and again.

What repeated work are we doing?

For a fixed start l, the sum of nums[l..r] is the sum of nums[l..r−1] plus one number. The brute force re-adds nums[l..r−1] for every end.

What information can we reuse?

Keep one running sum for each start. When r grows, add one number. Each number is added once per start.

New approach

Idea

For a fixed start l, moving the end from r to r + 1 adds exactly one number. So keep one running sum per start and never add the same number twice for that start.

Thinking process

1
The brute force adds nums[l] … nums[r] from scratch for every end r.
2
Look at start 1 in [-2, 1, -3, 4]. The sums for ends 1, 2, 3 are 1, then 1 + (-3) = -2, then -2 + 4 = 2. Each sum is the one before plus one number.
3
So for each start, begin a running sum at 0, add nums[r] as r grows, and check the sum each time.
4
From start 1 the best is 2, from the run [1, -3, 4]. Repeat for every start and keep the largest.

Code & Implementation

better.cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int best = INT_MIN;

        for (int l = 0; l < n; l++) {
            // One running sum per start. Moving r right adds one number,
            // so nothing in nums[l..r-1] is added again.
            int sum = 0;
            for (int r = l; r < n; r++) {
                sum += nums[r];
                best = max(best, sum);
            }
        }
        return best;
    }
};

Complexity

Time O(N^2)Space O(1)

Two nested loops with one addition per pair. For n = 10^5 that is about 5 · 10^9 additions, still too slow for the limit.

Optimized approach

Idea

Start from brute force

Brute force tries every (start, end) pair. Kadane looks at each end once and keeps only the best run that ends there.

Find the repeated work

The best run that ends at index i is built from the best run that ends at i − 1. The brute force rebuilds those runs from scratch for every start.

Define the state — what variables do I need?

cur: The largest sum of a subarray that ends at the current index. It is always a real, non-empty subarray.
best: The largest `cur` seen at any index so far. This is the answer at the end.
i: The current index. Every subarray ends at exactly one index, so checking every `i` covers them all.

Define validity

cur is always the best sum of a subarray that ends exactly at the current index, so it is a valid candidate for the answer at every step.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop (i = 0)

cur = best = nums[0]

A subarray must hold at least one number, so the first number is the only choice.

Each index i ≥ 1

cur = max(nums[i], cur + nums[i])

Either start fresh at nums[i], or extend the best run that ended at i − 1. The proof is in whyItWorks.

After each update

best = max(best, cur)

The answer may end at any index, so compare the best run ending at each index.

What does the current window add to the answer?

cur is the best run that ends at this index. If it beats best, it becomes the new answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        // cur  = best sum of a subarray that ends at the current index.
        // best = largest cur seen so far.
        // Start at nums[0]: a subarray needs at least one number.
        int cur = nums[0];
        int best = nums[0];

        for (int i = 1; i < n; i++) {
            // Restart at nums[i], or extend the run that ended at i - 1.
            cur = max(nums[i], cur + nums[i]);
            best = max(best, cur);
        }
        return best;
    }
};

Complexity

Time O(N)Space O(1)

One pass. Only cur and best are stored.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Add up every subarray from scratch and keep the largest sum	O(N^3)	O(1)
Better	Fix the start, grow the end one step at a time, keep one running sum	O(N^2)	O(1)
Optimal	Track the best run that ends at each index: extend it or restart	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous subarray”The answer is a run of neighbours. Think of the best run that ends at each index.
“largest sum”A sum can be updated in O(1): add the new number, or drop the old run and start again.
“at least one number”The answer can be negative, so the start value is a real number, never 0.

Contiguous subarray+maximize the sum+each index: extend or restart→Kadane's algorithm (Maximum subarray)

This is the anchor of the Maximum subarray sub-pattern. The length of the run is free, so the only decision at each index is extend or restart. The next three questions keep this rule and change the comparison: the smallest sum, the absolute sum, and one deletion.

Don't make this mistake

Pattern confusion: resetting to 0 when the sum goes negative

✗ int cur = 0, best = 0; for (int x : nums) { cur += x; best = max(best, cur); if (cur < 0) cur = 0; }

✓ int cur = nums[0], best = nums[0]; for (int i = 1; i < n; i++) { cur = max(nums[i], cur + nums[i]); best = max(best, cur); }

Resetting to 0 lets cur become an empty run. On the dry run [-2, 1, -3, 4, -1, 2, 1, -5, 4] it still prints 6, so the bug hides. But at index 2 it sets cur = 0, while the correct run ending there is −2. On [-3, -1, -2] it prints 0, but the answer is −1, the largest single number.

Adding every positive number

✗ int total = 0; for (int x : nums) if (x > 0) total += x;

This picks numbers from anywhere, so it finds a subsequence, not a subarray. On the dry run it gives 1 + 4 + 2 + 1 + 4 = 12, which skips the −3, −1 and −5 in between. The answer must be one run of neighbours, which is 6.

Checking only the last cur

✗ for (...) cur = max(nums[i], cur + nums[i]); return cur;

✓ best = max(best, cur); // at every index ... return best;

The best run can end in the middle of the array. On the dry run the last cur is 5, for the run [4, −1, 2, 1, −5, 4]. The best run, [4, −1, 2, 1], ends at index 6 and sums to 6.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture