Dynamic Programming from Zero to Hero: The Matrix of Patterns

#algorithms #datastructures #programming #coding

The Quest Begins (The "Why")

I still remember the first time I stared at a LeetCode problem titled “Maximum Subarray” and felt my brain short‑circuit. The brute‑force solution was obvious: try every possible start and end, compute the sum, keep the biggest. O(n²) felt okay for tiny arrays, but the moment the input grew to 10⁵ elements my laptop started sounding like a jet engine. I was stuck in a loop of “just try harder” and getting nowhere fast.

Why did this feel like a boss fight? Because the problem screamed “there’s a smarter way” but I couldn’t see the pattern. I kept thinking, “If I could just reuse work I’ve already done, I’d save a ton of time.” That’s the heart of dynamic programming: optimal substructure plus overlapping subproblems. Once you spot those two traits, the solution almost writes itself.

The Revelation (The Insight)

The magic trick is simple: instead of recomputing the sum of every subarray from scratch, we keep track of the best sum that ends at the current position. Let’s call that curr. When we look at the next element x, we have two choices:

Extend the previous subarray (curr + x)
Start fresh at x (if the previous sum was dragging us down)

So curr = max(x, curr + x). The overall answer is the maximum curr we ever see.

Why does this work? Because any optimal subarray ending at position i must either be the element i alone or the optimal subarray ending at i‑1 plus a[i]. If we knew the best sum ending at i‑1, we can compute the best ending at i in O(1). No need to revisit earlier indices—overlap eliminated. This is the classic Kadane’s algorithm, a pure DP formulation with O(n) time and O(1) space.

Wielding the Power (Code & Examples)

The Struggle – Brute Force

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

O(n²) time, O(1) space. Works for interview warm‑ups but times out on anything beyond a few hundred elements.

The Victory – Kadane (DP)

def max_subarray(nums):
    # curr = best sum ending at current index
    # best = overall best seen so far
    curr = best = nums[0]
    for x in nums[1:]:
        # either start new subarray at x, or extend previous one
        curr = max(x, curr + x)
        best = max(best, curr)
    return best

Why it’s O(n): The loop visits each element once, doing constant work per iteration. No nested loops, no recursion depth—just a single pass.

Common Traps

Trap	What happens	How to avoid
Forgetting to initialize `curr` and `best` with `nums[0]`	If the array contains all negatives, starting at 0 gives a wrong answer (empty subarray isn’t allowed)	Seed both variables with the first element
Using `curr = max(0, curr + x)`	Allows an empty subarray, which the problem usually forbids	Stick to `max(x, curr + x)` – you must take at least one element
Over‑thinking space	Trying to keep an entire DP table when only the previous value is needed	Remember we only need the last `curr`; O(1) space is enough

Real‑World Interview Flavors

Best Time to Buy and Sell Stock I (LeetCode 121)

Problem: Given daily prices, find the max profit from one buy‑sell pair.

DP view: Treat price[i] - min_price_so_far as the “subarray sum” ending at day i. Keep min_price and update max_profit = max(max_profit, price[i] - min_price). Same O(n) logic, just a different framing.
House Robber (LeetCode 198)

Problem: Max money from non‑adjacent houses.

DP view: dp[i] = max(dp[i-1], dp[i-2] + money[i]). Again, only the last two states matter → O(n) time, O(1) space if you roll variables.

Both problems reduce to the same pattern: keep the best answer that ends at the current position, then decide whether to extend or reset. Recognizing that pattern is the real power‑up.

Why This New Power Matters

Once you internalize Kadane’s idea, a whole class of “pick a contiguous segment” problems becomes trivial. You stop grinding nested loops and start spotting the state you need to carry forward. Interviews stop feeling like guess‑work and start feeling like applying a trusted spell.

More importantly, you’ve leveled up your algorithmic intuition: you now ask “What’s the optimal substructure? What am I recomputing?” before writing a single line of code. That mindset transfers to harder DP knapsacks, string edits, tree DP—you name it.

Your Next Quest

Here’s a challenge to seal the deal: Solve “Maximum Sum Circular Subarray” (LeetCode 918). Hint: the answer is either the normal Kadane result or the total sum minus the minimum subarray sum (which you can get with a Kadane‑style pass on the negated array). Give it a try, and when it clicks, you’ll feel like you just defeated the final boss and earned the DP badge of honor.

Happy coding, and may your subarrays always be maximal! 🚀

DEV Community