The Matrix: Dynamic Programming from Zero to Hero – Finding the One Subarray

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 subarray with the largest sum.” My brain instantly flashed to a brute‑force double loop, O(n²), and I could feel the sweat start to bead. I thought, “There’s gotta be a smarter way—this feels like I’m trying to solve a Rubik’s cube by peeling off stickers.” After a few failed attempts, I realized I was missing the core idea behind dynamic programming: optimal substructure. Once I grasped that, the problem transformed from a nightmare into a puzzle I could solve in my head while waiting for my coffee to brew.

The Revelation (The Insight)

The magic of Kadane’s algorithm isn’t some obscure trick; it’s a direct translation of the DP recurrence into a couple of variables.

Let’s break it down. Suppose we’re at index i and we already know the best subarray sum that ends at i‑1. Call that curr. To extend the subarray to include nums[i], we have two choices:

1. Start fresh at nums[i] (if the previous sum is dragging us down).
2. Extend the previous subarray by adding nums[i] to curr.

So the best sum ending at i is max(nums[i], curr + nums[i]).

The overall answer is simply the maximum of all those “ending‑here” sums.

Why does this work? Because any optimal subarray must end somewhere. If we know the best possible sum for every possible ending position, the global optimum is just the max of those. The DP table collapses to two scalars—curr (the best sum ending at the current index) and best (the best sum seen so far). No need to store an entire array; we’re literally carrying the solution forward like a hero carrying a sword through a dungeon.

Wielding the Power (Code & Examples)

The Struggle: Brute Force

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

O(n²) time, O(1) space. Works, but for an array of size 10⁵ it’s like trying to win a race with a bicycle when everyone else has a jetpack.

The Victory: Kadane’s Algorithm

def max_subarray_kadane(nums):
    # Edge case: empty array (though interview constraints usually guarantee >=1)
    if not nums:
        return 0

    curr = best = nums[0]          # start with the first element
    for x in nums[1:]:
        # Either extend the previous subarray or start new at x
        curr = max(x, curr + x)
        best = max(best, curr)
    return best

Why it’s O(n): We touch each element exactly once, doing a constant amount of work per step. No nested loops, no recursion depth—just a simple forward sweep.

Space: Only two integers, so O(1).

Common Traps

• All‑negative arrays: If you initialize curr or best to 0, you’ll incorrectly return 0 (the empty subarray) when the answer should be the largest (least negative) element. Starting with nums[0] avoids that.
• Forgetting to update best inside the loop: The answer might be found mid‑array; you need to check after each update of curr.

Interview‑Style Variations

1. Maximum Subarray (LeetCode 53) – straight‑up Kadane.
2. Best Time to Buy and Sell Stock (LeetCode 121) – treat prices[i] - min_price_sofar as the “current profit” and keep the max. It’s the same pattern: maintain the best value ending at the current point and a global best.

Both reduce to a single pass, O(n) time, O(1) space. Once you see the pattern, a dozen DP‑flavored questions become trivial.

Why This New Power Matters

Mastering Kadane’s algorithm does more than let you ace a subarray question—it rewires your intuition for DP. You start spotting the “ending‑here” state in problems about sequences, profits, or even game scores. The next time you see a prompt that asks for “maximum … with a contiguous constraint,” you’ll think, “Ah, I just need a running best and a global best.”

That shift from “I’ll try every possibility” to “I’ll carry forward the best so far” is the heart of dynamic programming. It’s the difference between brute force and elegance, between grinding and gliding. And the best part? The same idea pops up in unexpected places—think of tracking the highest score in a rhythm game where you can only keep a streak if the next note doesn’t break your combo.

Your Turn

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

Given an array of daily temperatures, find the maximum temperature increase you could achieve by buying on one day and selling on a later day (you must buy before you sell).

Implement it in O(n) time, O(1) space, and drop your solution in the comments. If you get stuck, remember the two‑variable pattern—curr and best.

Go forth, conquer those interview dragons, and may your subarrays always be maximal! 🚀