Kadane’s Algorithm — Negatives Are Useless

Imagine you’re given the following array:

[-1, 3, -4, 5, 7, 3, -6, 8]

Your task is to find the maximum possible contiguous subarray sum.

A brute-force solution would check every possible subarray and calculate its sum. While this works, it becomes extremely inefficient as the size of the array grows.

So, how can we do better?

The Core Idea

Let’s start with the first element:

Current Sum = -1

Now we move to the next element, 3.

We have two choices:

Option 1: Continue the current subarray

Current Sum = -1 + 3 = 2

Option 2: Start a brand new subarray

Current Sum = 3

Clearly, the second option is better.

Why carry a negative value into the future when we can start fresh with a larger sum?

This leads us to the key insight behind Kadane’s Algorithm:

If the running sum ever becomes negative, discard it and start a new subarray.

A negative running sum is simply extra baggage. It can never help create a larger maximum sum in the future.

What Does Kadane’s Algorithm Really Do?

At every element, it asks a simple question:

Should I continue the current subarray?

or

Should I start a new subarray from this element?

Whichever gives a larger sum becomes the new current sum.

That’s the entire algorithm.

Dry Run

Consider the array:

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

Initialize:

Current Sum = 0

Maximum Sum = -∞

Element = -2

Current Sum = 0 + (-2) = -2

Maximum Sum = -2

Current Sum is negative, so we discard it and start fresh.

Element = 1

Current Sum = 1

Maximum Sum = 1

Element = -3

Current Sum = 1 + (-3) = -2

Current Sum becomes negative again, so we reset it.

Element = 4

Current Sum = 4

Maximum Sum = 4

Element = -1

Current Sum = 4 + (-1) = 3

Maximum Sum = 4

Element = 2

Current Sum = 3 + 2 = 5

Maximum Sum = 5

Element = 1

Current Sum = 5 + 1 = 6

Maximum Sum = 6

Final Answer = 6

The maximum subarray is:

[4, -1, 2, 1]

whose sum is 6.

Why Does It Work?

Kadane’s Algorithm works because it never carries a harmful negative running sum into the future.

Whenever the current sum becomes negative, it is immediately discarded.

This simple observation allows us to process the entire array in a single pass while still guaranteeing the correct answer.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Final Takeaway

Whenever you encounter phrases such as:

• Maximum Subarray Sum
• Largest Contiguous Sum
• Maximum Sum of a Continuous Segment

there’s a good chance Kadane’s Algorithm is the pattern hiding behind the problem.

Sometimes the most powerful algorithms aren’t built on complicated mathematics.

They’re built on a simple observation:

Negative sums are useless.

Kadane’s Algorithm Summarized