The Matrix: Dynamic Programming from Zero to Hero – Kadane's Algorithm

The Quest Begins (The "Why")

I still remember the first time I walked into a coding interview and saw the prompt: “Given an array of integers, find the contiguous sub‑array with the largest sum.” My brain instantly flashed to the brute‑force solution — two nested loops, O(n²), and a sinking feeling that I was about to get stuck in a loop like Neo dodging bullets in the lobby scene. I spent twenty minutes scribbling arrays, trying every start‑end pair, and watching the clock tick down. When the interviewer finally said, “There’s a linear‑time solution,” I felt like I’d just discovered a secret cheat code.

That moment sparked my quest: Why does a simple, single‑pass algorithm solve a problem that looks like it needs to examine every possible sub‑array? If I could uncover the intuition, I’d not only ace this interview question but also gain a pattern that shows up in countless other DP challenges (stock trading, maximum profit, even some string problems).

The Revelation (The Insight)

The magic behind Kadane’s algorithm is deceptively simple: the best sub‑array ending at position i either extends the best sub‑array ending at i‑1 or starts fresh at i.

Think of it like a hero on a quest. At each step, the hero asks: “Should I keep walking the path I’m on, or should I turn back and start a new adventure from here?” If the current path (the sum so far) is dragging me down (i.e., it’s negative), it makes sense to abandon it and begin anew at the current treasure. Otherwise, I keep adding the current treasure to my haul.

Why does this guarantee the global optimum? Because any optimal sub‑array must end somewhere. When we reach that ending index, the algorithm has already considered the best possible sum that could end there — either by extending the previous best or by starting at that index. Since we keep track of the maximum of all those “best‑ending‑here” values, we never miss the true optimum.

In short, the algorithm collapses an exponential‑looking search into a linear scan by exploiting two properties:

1. Optimal substructure – the solution to a sub‑problem (best sum ending at i) builds directly from the solution to the previous sub‑problem.
2. Greedy choice – at each step we make the locally optimal decision (keep or reset) that never hurts the chance of a globally optimal solution.

That’s why it works, not just how to type it.

Wielding the Power (Code & Examples)

The Struggle: Brute‑Force O(n²)

def max_subarray_brute(nums):
    best = float('-inf')
    for i in range(len(nums)):
        current = 0
        for j in range(i, len(nums)):
            current += nums[j]
            best = max(best, current)
    return best

Problems:

• Two loops → O(n²) time, O(1) space.
• For an array of size 10⁵, you’re looking at ~10¹⁰ operations — definitely not interview‑friendly.

The Victory: Kadane’s O(n)

def max_subarray_kadane(nums):
    # best_ending_here = max sum of a sub‑array that MUST end at current index
    # best_so_far      = max sum seen anywhere so far
    best_ending_here = best_so_far = nums[0]

    for x in nums[1:]:
        # Either extend the previous sub‑array or start fresh at x
        best_ending_here = max(x, best_ending_here + x)
        # Update the global answer if we found a new peak
        best_so_far = max(best_so_far, best_ending_here)

    return best_so_far

Why this is O(n): One pass, constant‑time work per element → O(n) time, O(1) space.

Interview Problem #1 – LeetCode 53: Maximum Subarray

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

Output: 6 (sub‑array [4,-1,2,1])

Running Kadane’s on this array:

idx	x	best_ending_here	best_so_far
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

The answer is 6, found in a single sweep.

Interview Problem #2 – LeetCode 121: Best Time to Buy and Sell Stock

Here we want the maximum profit from one buy‑sell pair. If we store daily prices, the profit from buying at the lowest price seen so far and selling today is price - min_price. This is exactly Kadane’s idea applied to the differences between consecutive days:

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0
    for p in prices:
        min_price = min(min_price, p)
        max_profit = max(max_profit, p - min_price)
    return max_profit

Same linear scan, same O(n) time, O(1) space.

Traps to Avoid

1. Forgetting the all‑negative case – If you initialize best_ending_here and best_so_far to 0, an array like [-3,-2,-1] would incorrectly return 0. Seed them with the first element (or -inf) to handle negatives correctly.
2. Thinking you need to store the sub‑array itself – The algorithm only needs the sum; retrieving the actual indices requires a tiny bit of extra bookkeeping (store start index when you reset). Don’t over‑engineer unless the prompt asks for the sub‑array.

Why This New Power Matters

Mastering Kadane’s algorithm does more than let you solve “maximum sub‑array” in an interview. It teaches you to spot DP problems where the state can be compressed to a single variable because the transition only depends on the immediate previous state. That insight unlocks:

• Stock‑trading variants (multiple transactions, cooldown, fee) – each is a tweak on the same linear scan.
• Maximum product sub‑array – you keep track of both max and min because a negative can flip signs.
• Longest alternating subsequence – similar “extend or reset” logic.

In short, you’ve added a versatile sword to your developer’s arsenal. The next time you see a problem that asks for “the best contiguous segment” or “the best profit over time,” you’ll hear that familiar inner voice: “Should I keep going or start fresh?” And you’ll answer it in O(n) time, O(1) space, with a smile.

Your Turn

Grab a piece of paper (or an IDE) and try this:

Given an array of integers, find the length of the longest contiguous sub‑array whose sum is divisible by k.

Hint: Transform the problem into a maximum‑distance‑between‑equal‑remainders challenge — you can still solve it in O(n) with a hash map.

If you crack it, drop your solution in the comments. I’d love to see how you wield the power of Kadane‑style thinking! Happy coding!