Dynamic Programming from Zero to Hero: patterns and templates – Leveling up like a Jedi

The Quest Begins (The "Why")

I still remember the first time I faced a coding interview question that asked for the maximum sum of a contiguous subarray. I stared at the array, tried brute‑force loops, and watched my solution crawl to O(n²) while the interviewer’s eyebrows rose higher with each passing second. I felt like I was swinging a wooden sword against a dragon—lots of effort, zero impact.

That frustration sparked a question: Is there a smarter way to reuse work we’ve already done? It turned out the answer was hiding in plain sight: dynamic programming isn’t just about filling tables; it’s about recognizing that the optimal solution to a problem depends on the optimal solution to a smaller piece of the same problem. Once I saw that pattern, the dragon started to look a lot less intimidating.

The Revelation (The Insight)

The algorithm that clicked for me was Kadane’s algorithm – the classic O(n) solution for the maximum subarray sum.

Why it works (the magic behind the code)

At its core, Kadane’s algorithm keeps two values while scanning the array once:

1. current_max – the best sum we can get ending at the current position.
2. global_max – the best sum we’ve seen anywhere so far.

The key insight is simple: if extending the previous subarray makes the sum worse than starting fresh at the current element, we drop the past and begin anew. Formally:

current_max = max(nums[i], current_max + nums[i])
global_max  = max(global_max, current_max)

Why does this guarantee optimality? Because any optimal subarray ending at position i either:

• consists only of nums[i] (we start new), or
• is the optimal subarray ending at i‑1 extended by nums[i].

By taking the max of those two possibilities we never discard a candidate that could be part of the final answer. The algorithm therefore explores exactly the set of subarrays that could be optimal, doing it in a single linear pass – O(n) time, O(1) space.

Wielding the Power (Code & Examples)

The Struggle (naïve attempt)

def max_subarray_bruteforce(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

Two nested loops → O(n²) time. Works, but times out on anything beyond a few thousand elements.

The Victory (Kadane’s)

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

    current_max = global_max = nums[0]

    for x in nums[1:]:
        # Either extend the previous subarray or start fresh at x
        current_max = max(x, current_max + x)
        # Update the best we've seen so far
        global_max = max(global_max, current_max)

    return global_max

Why this feels like a power‑up:

• One pass → O(n).
• Only two integer variables → O(1) extra space.
• No recursion, no table, just pure intuition.

Common trap #1 – Forgetting to handle all‑negative arrays

If you initialise current_max and global_max to 0, an array like [-3, -2, -7] would incorrectly return 0. The fix is to seed both with the first element (as shown) or to use float('-inf') and update inside the loop.

Common trap #2 – Mis‑placing the update order

Some versions write global_max = max(global_max, current_max) before updating current_max. That uses the previous iteration’s current_max and can miss a better subarray that ends at the current index. The order shown above guarantees we consider the subarray that ends at the current position first.

A Second Interview Flavor – Best Time to Buy and Sell Stock I

The problem: given daily stock prices, find the maximum profit from one buy‑sell transaction. It’s essentially the same pattern: we want the largest difference where the sell comes after the buy.

def max_profit(prices):
    if not prices:
        return 0

    min_price = prices[0]      # best buy price seen so far
    max_profit = 0

    for price in prices[1:]:
        # profit if we sell today having bought at min_price
        max_profit = max(max_profit, price - min_price)
        # update the cheapest price seen so far
        min_price = min(min_price, price)

    return max_profit

Again, one pass, O(n) time, O(1) space. The “why” mirrors Kadane’s: we keep the best state (lowest price) and compute the best outcome (profit) from that state at each step.

Why This New Power Matters

Mastering Kadane’s paradigm does more than solve a single interview question. It trains you to spot optimal substructure and overlapping subproblems everywhere:

• You can adapt it to find the maximum sum subarray with a length constraint.
• You can turn it into a solution for “maximum product subarray” by tracking both min and max.
• It’s the mental model behind many greedy‑ish DP tricks that appear in contests and real‑world problems (e.g., budgeting, signal processing, bio‑informatics).

When you internalise the idea of “keep the best state so far and update it with the next piece of data,” you stop memorising patterns and start creating them. That shift turns a nerve‑racking interview into a chance to showcase genuine problem‑solving flair.

---

Your turn: Grab an array of integers (maybe your daily step counts) and try to compute not just the max sum, but also the indices of that subarray in O(n) time. Post your solution or a snippet in the comments—I’d love to see how you wield the power! 🚀