LeetCode #53: Maximum Subarray — Master Kadane’s Algorithm

LeetCode Problem: Maximum Subarray
Difficulty: Medium
Topics: Array, Dynamic Programming, Greedy, Divide and Conquer
Series: LeetCode Interview Preparation — From Beginner to Expert

If you've solved our previous problems, you've already learned three important interview ideas:

• Two Sum → Hash Map
• Best Time to Buy and Sell Stock → Running Minimum + Maximum Answer
• Contains Duplicate → Hash Set

Now we're taking a step up.

Today's problem is one of the most famous array problems in technical interviews:

LeetCode #53 — Maximum Subarray

The problem introduces one of the most important algorithms you should know for coding interviews:

Kadane's Algorithm

It is a beautiful example of how a problem that appears to require checking many possibilities can be reduced to a single O(n) scan.

The Problem

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

A subarray must contain at least one element, and the elements must be contiguous.

Example

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

Output:
6

The maximum-sum subarray is:

[4, -1, 2, 1]

Its sum is:

4 + (-1) + 2 + 1 = 6

Therefore:

Answer = 6

What Exactly Is a Subarray?

This distinction is extremely important.

A subarray contains consecutive elements.

For:

[1, 2, 3, 4]

these are valid subarrays:

[1]
[2]
[3]
[4]

[1,2]
[2,3]
[3,4]

[1,2,3]
[2,3,4]

[1,2,3,4]

But:

[1,3]

is not a subarray because 1 and 3 are not adjacent.

Subarray vs Subsequence

This is a common interview trap.

Subarray

Elements must be contiguous.

[2, 3, 4]

Subsequence

Elements don't necessarily have to be contiguous.

For example:

[2, 4]

can be a subsequence of:

[2, 3, 4]

but it is not a subarray.

Always clarify this distinction.

First Approach: Brute Force

The simplest approach is to generate every possible subarray and calculate its sum.

For example:

[-2, 1, -3, 4]

We could consider:

[-2]
[-2, 1]
[-2, 1, -3]
[-2, 1, -3, 4]

[1]
[1, -3]
[1, -3, 4]

[-3]
[-3, 4]

[4]

and keep track of the largest sum.

Brute-Force Solution

One straightforward implementation is:

def maxSubArray(nums):
    max_sum = float('-inf')

    for i in range(len(nums)):
        current_sum = 0

        for j in range(i, len(nums)):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)

    return max_sum

Notice something useful here.

We don't recalculate the entire subarray sum every time.

Instead:

current_sum += nums[j]

lets us reuse the previous sum.

This improves the brute-force approach from a potential O(n³) implementation to:

O(n²)

Complexity of Brute Force

We use two nested loops.

Therefore:

Time Complexity: O(n²)
Space Complexity: O(1)

This is better than generating every subarray and summing each one from scratch, but it can still be too slow for large inputs.

We need to think differently.

The Key Question

Consider this array:

[-2, 1, -3, 4, -1, 2, 1]

Suppose we're currently considering:

4

We have two choices.

Choice 1

Start a new subarray:

[4]

Sum:

4

Choice 2

Extend the previous subarray:

[..., 4]

The question becomes:

Is the previous subarray helping us or hurting us?

If the previous sum is negative, carrying it forward makes our current sum smaller.

Therefore:

If the previous running sum is negative, throw it away and start fresh.

This is the central idea behind Kadane's Algorithm.

The Core Idea

At every element, we ask:

Should I:

1. Start a new subarray here?

OR

2. Extend the previous subarray?

Mathematically:

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

That's Kadane's Algorithm.

Why Does This Work?

Suppose:

current_sum = -5

and the next number is:

10

If we extend the previous subarray:

-5 + 10 = 5

But starting fresh gives:

10

Clearly:

10 > 5

So the negative prefix is hurting us.

We should discard it.

The Optimized Solution

def maxSubArray(nums):
    current_sum = nums[0]
    max_sum = nums[0]

    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum

That's Kadane's Algorithm.

Only a few lines.

But the reasoning behind those lines is extremely important.

Understanding the Two Variables

We maintain:

current_sum

and:

max_sum

current_sum

The maximum sum of a subarray ending at the current position.

max_sum

The maximum subarray sum we've seen anywhere in the array so far.

This distinction is critical.

Dry Run

Consider:

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

Initial values:

current_sum = -2
max_sum = -2

Now process the array.

Number = 1

We compare:

1

with:

-2 + 1 = -1

Choose:

1

So:

current_sum = 1
max_sum = 1

Number = -3

Compare:

-3

with:

1 + (-3) = -2

Choose:

-2

So:

current_sum = -2
max_sum = 1

Number = 4

Compare:

4

with:

-2 + 4 = 2

Choose:

4

So:

current_sum = 4
max_sum = 4

The negative sum was discarded.

Number = -1

Compare:

-1

with:

4 + (-1) = 3

Choose:

3

Now:

current_sum = 3
max_sum = 4

Number = 2

Compare:

2

with:

3 + 2 = 5

Choose:

5

Now:

current_sum = 5
max_sum = 5

Number = 1

Compare:

1

with:

5 + 1 = 6

Choose:

6

Now:

current_sum = 6
max_sum = 6

We've found:

[4,-1,2,1]

with sum:

6

Number = -5

Compare:

-5

with:

6 + (-5) = 1

Choose:

1

So:

current_sum = 1
max_sum = 6

Number = 4

Compare:

4

with:

1 + 4 = 5

Choose:

5

But:

max_sum = 6

still wins.

Final answer:

6

Dry Run Table

Final answer:

6

The Most Important Line

This line contains the entire algorithm:

current_sum = max(num, current_sum + num)

Read it as:

"Should I start a new subarray with this number, or should I append this number to the existing subarray?"

If:

num > current_sum + num

starting fresh is better.

Otherwise, extending the current subarray is better.

Another Way to Think About It

Imagine you're carrying a backpack.

Your current subarray has a weight:

current_sum

If that accumulated sum becomes strongly negative, it's hurting every future number.

For example:

-10 + 5 = -5

You would rather start at:

5

instead of carrying:

-10

So Kadane's Algorithm continuously asks:

"Is my past helping me or hurting me?"

If it's hurting:

Start over.

If it's helping:

Continue.

Why We Need max_sum

You might wonder:

"Why not just return current_sum?"

Because current_sum represents the best subarray ending at the current position.

The global best could have occurred earlier.

Consider:

[5, -10, 2]

The maximum subarray is:

[5]

with:

5

But by the end:

current_sum = 2

Therefore we need:

max_sum

to remember the best answer we've seen.

Important Edge Case: All Negative Numbers

This is where many beginners make mistakes.

Consider:

nums = [-8, -3, -6, -2, -5, -4]

The answer is:

-2

Why?

Because the subarray must contain at least one element.

We cannot return:

0

The maximum subarray is:

[-2]

Therefore, initializing with:

current_sum = nums[0]
max_sum = nums[0]

is important.

Don't blindly initialize:

max_sum = 0

That would produce an incorrect answer for all-negative arrays.

Common Mistake #1: Resetting to Zero

You may see implementations like:

current_sum += num

if current_sum < 0:
    current_sum = 0

This version is common and can work under certain formulations, but if the problem requires handling all-negative arrays correctly, you need to make sure the global maximum is tracked appropriately.

The more explicit formulation:

current_sum = max(num, current_sum + num)

is often easier to reason about and avoids accidentally losing the answer when every number is negative.

Common Mistake #2: Confusing Subarray With Subsequence

For:

[4, -1, 2, 1]

you cannot arbitrarily skip elements.

The selected elements must remain contiguous.

That's why:

[4, 2, 1]

is not a valid subarray of the original sequence.

Common Mistake #3: Returning the Maximum Element

For:

[-2,1,-3,4,-1,2,1]

the largest individual element is:

4

But the maximum subarray sum is:

6

because combining:

4 + (-1) + 2 + 1

produces something larger.

Complexity Analysis

Kadane's Algorithm scans the array exactly once.

For every element, we perform constant-time operations.

Therefore:

Time Complexity

O(n)

Space Complexity

O(1)

This is a major improvement over the brute-force:

O(n²)

solution.

Can We Find the Actual Subarray?

Yes.

The basic problem asks only for the maximum sum.

But an interviewer might ask:

"Can you also return the subarray that produces that maximum?"

Absolutely.

We can track:

start
end
temporary_start

Returning the Maximum Subarray

def maxSubArray(nums):
    current_sum = nums[0]
    max_sum = nums[0]

    start = 0
    end = 0
    temp_start = 0

    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            temp_start = i
        else:
            current_sum += nums[i]

        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i

    return max_sum, nums[start:end + 1]

For:

[-2,1,-3,4,-1,2,1,-5,4]

we get:

6
[4,-1,2,1]

The complexity remains:

O(n)

time and:

O(1)

extra space, excluding the returned subarray.

Dynamic Programming Perspective

Kadane's Algorithm can be understood as a Dynamic Programming solution.

Define:

dp[i]

as:

The maximum sum of a subarray ending at index i.

Then:

dp[i] = max(
    nums[i],
    dp[i-1] + nums[i]
)

The answer is:

max(dp)

This is the DP recurrence.

But notice something interesting.

We only need:

dp[i-1]

to calculate:

dp[i]

We don't need the entire DP array.

Therefore, we compress the DP solution into:

current_sum

This is a very important optimization pattern.

Full DP Version

For learning purposes:

def maxSubArray(nums):
    dp = [0] * len(nums)

    dp[0] = nums[0]

    for i in range(1, len(nums)):
        dp[i] = max(nums[i], dp[i - 1] + nums[i])

    return max(dp)

Complexity:

Time: O(n)
Space: O(n)

Kadane's optimized version reduces space to:

O(1)

Kadane's Algorithm Pattern

The pattern is:

Current State
      ↓
Start New?
   OR
Extend Previous?
      ↓
Keep Better Option
      ↓
Update Global Answer

This idea appears in many optimization problems.

How to Recognize Kadane's Algorithm

In an interview, look for problems involving:

• Maximum subarray sum
• Best contiguous segment
• Maximum gain from consecutive values
• Largest sum of consecutive elements
• Minimum subarray sum
• Maximum product subarray
• Best contiguous range

When you see:

"Find the maximum/minimum sum of a contiguous subarray."

Kadane's Algorithm should immediately come to mind.

Maximum vs Minimum Subarray

The same reasoning can be adapted to find the minimum subarray sum.

Instead of:

max(...)

you use:

min(...)

Conceptually:

current_sum = min(num, current_sum + num)

Again, the question becomes:

Should I start fresh or extend the previous segment?

A Connection With Our Previous Problems

Look at the progression of our series.

Problem #1 — Two Sum

We learned:

Hash Map

Problem #2 — Best Time to Buy and Sell Stock

We learned:

Running Minimum
+
Global Maximum

Problem #3 — Contains Duplicate

We learned:

Hash Set

Problem #4 — Maximum Subarray

We're learning:

Running State
+
Local Optimization
+
Global Answer

Notice what's happening.

We're not just solving random LeetCode questions.

We're building a pattern library.

That's how you should approach interview preparation.

Interview Follow-Up Questions

An interviewer can turn this Easy-looking concept into several harder questions.

Follow-Up 1

Return the actual subarray instead of only the sum.

Follow-Up 2

Find the minimum subarray sum.

Follow-Up 3

Find the maximum product subarray.

This is LeetCode #152 and introduces a very interesting complication because negative numbers can turn into positive products.

Follow-Up 4

Find the maximum circular subarray sum.

This leads to LeetCode #918.

Follow-Up 5

Find the maximum subarray with additional constraints.

Now you may need:

• Prefix sums
• Deques
• Dynamic programming
• Sliding windows

depending on the constraint.

Interview Explanation Template

If you're asked this problem in an interview, don't immediately start coding.

Explain your thought process.

A strong explanation would be:

"The brute-force solution checks every possible subarray and takes O(n²). We can optimize this using Kadane's Algorithm. For each position, I maintain the maximum sum of a subarray ending at that position. The choice is either to start a new subarray with the current element or extend the previous subarray. So the recurrence is max(nums[i], current_sum + nums[i]). I also maintain a global maximum because the best subarray may end before the final element."

Then code it.

This demonstrates both:

Algorithmic knowledge + reasoning ability.

Interview Cheat Sheet

Problem:
Find the maximum sum of a contiguous subarray.

Brute Force:
Generate every subarray.

Time:
O(n²)

Optimized:
Kadane's Algorithm.

Maintain:

current_sum
max_sum

For each number:

current_sum =
    max(num, current_sum + num)

max_sum =
    max(max_sum, current_sum)

Time:
O(n)

Space:
O(1)

Practice Challenges

Before moving forward, try solving these variations:

Challenge 1

Return the actual maximum-sum subarray.

Challenge 2

Find the minimum subarray sum.

Challenge 3

Find the maximum product subarray.

Challenge 4

Find the maximum circular subarray sum.

Challenge 5

Find the longest subarray whose sum satisfies a given condition.

These will prepare you for more advanced array and dynamic programming problems.

Final Takeaway

Kadane's Algorithm is one of those algorithms that looks almost magical when you first encounter it.

A problem that seems to require examining:

O(n²)

possible subarrays can be solved in:

O(n)

with only a couple of variables.

But the real lesson isn't the formula.

It's the question behind the formula:

"Should I continue with what I've built so far, or is it better to start fresh?"

That question appears in many optimization problems.

Once you learn to identify that decision, Kadane's Algorithm stops looking like a trick and starts looking like a natural consequence of the problem.

And that's exactly the goal of this Kairos Coders series:

Don't memorize solutions. Learn the patterns that let you discover solutions.