From brute force to optimal: leveling up like a Jedi

The Quest Begins (The "Why")

I still remember the first time I tried to solve the “maximum subarray sum” problem on a coding interview. I stared at the array, thought “hey, I’ll just check every possible subarray,” and started nesting loops like I was building a fortress. Three loops later, my solution was O(n³) and my brain felt like it had been hit by a blaster bolt. I kept telling myself, “It works for the small test cases, so it must be fine.” Spoiler: it wasn’t. The moment the interviewer slid over a test with 10⁵ elements and my program froze, I felt that sinking feeling you get when you realize you’ve been brute‑forcing a puzzle that actually has a elegant shortcut.

That experience kicked off a quest: how do top coders look at a problem and instantly see the leash that turns a brute‑force mess into a clean, optimal solution? I wanted the mental framework, not just a trick for one specific question. So I dug into blogs, watched talks, and—most importantly—practiced the shift in perspective that makes the “aha!” click.

The Revelation (The Insight)

The breakthrough wasn’t a new algorithm; it was a change in how I framed the problem. Instead of asking “what do I need to compute for every possible slice?” I started asking “what information do I need to keep track of as I sweep through the array once?”

Think of it like this: when you’re playing a platformer and you need to know the highest point you’ve reached so far, you don’t recompute the entire history each step—you just keep a running max. The same idea applies to many “range” problems: maintain a piece of state that summarizes everything you’ve seen, update it in O(1) per element, and let the answer emerge from that state.

For maximum subarray sum, the state is two numbers:

• current – the best sum of a subarray that ends at the current position.
• best – the best sum seen anywhere so far.

When you read a new element x, you either extend the previous subarray (current + x) or start fresh at x (if the previous sum would drag you down). Then you update best with the larger of current and best. One pass, O(n) time, O(1) space.

The “aha!” hit me when I realized the brute‑force approach was essentially recomputing the same partial sums over and over. By caching the best ending‑here sum, I avoided all that redundant work. It felt like unlocking the secret level in Celeste—suddenly the path was clear, and the next jump was trivial.

Wielding the Power (Code & Examples)

Let’s see the transformation in code. First, the brute‑force version (the “dragon” we’re slaying):

def max_subarray_bruteforce(arr):
    n = len(arr)
    best = float('-inf')
    for i in range(n):
        for j in range(i, n):
            # compute sum of arr[i:j+1] each time
            s = sum(arr[i:j+1])
            if s > best:
                best = s
    return best

Why it hurts: the inner sum is O(n), and we call it for every (i, j) pair → O(n³). For even modest inputs it crawls.

Now the optimal version, applying the insight:

def max_subarray_kadane(arr):
    best = float('-inf')
    current = 0          # best sum of a subarray ending at the previous index
    for x in arr:
        # either extend the previous subarray or start new at x
        current = max(x, current + x)
        best = max(best, current)
    return best

Traps to avoid (the “enemy patrols” on our quest):

1. Resetting current to zero when all numbers are negative. If you set current = 0 and then do current = max(0, current + x), you’ll incorrectly return 0 for an array like [-3, -2, -7]. The fix is to let current start at the first element (or use float('-inf') and the max(x, current + x) pattern shown above).
2. Forgetting to update best inside the loop. If you only update after the loop, you’ll miss the case where the best subarray ends at the last element.

Run both on a larger test:

import random, time
big = [random.randint(-1000, 1000) for _ in range(200_000)]

t0 = time.time()
print(max_subarray_bruteforce(big[:2000]))  # slice to keep it survivable
print("brute force time:", time.time() - t0)

t1 = time.time()
print(max_subarray_kadane(big))
print("Kadane time:", time.time() - t1)

You’ll see the brute‑force version stall (or take seconds on a tiny slice), while Kadane finishes in a blink—linear time, constant space.

Why This New Power Matters

Adopting this “running state” mindset opens doors far beyond maximum subarray. Sliding window problems, longest substring without repeating characters, stock‑profit‑maximization, even certain dynamic programming transitions all reduce to: what minimal information do I need to keep while scanning?

When you internalize it, you stop seeing problems as “nested loops waiting to happen” and start seeing them as “what can I update in O(1) per step?” That shift turns intimidating interview questions into quick, confident solutions—and it makes your everyday code cleaner and faster.

Imagine you’re debugging a log‑processing pipeline that currently scans the file three times to compute aggregates. By spotting the opportunity to keep a running sum, min, and max, you cut the runtime from O(3n) to O(n) and free up resources for the next feature. That’s the kind of impact that feels like leveling up your character stats in an RPG—except the XP is real‑world performance gains.

Your turn: Grab a problem you’ve solved with brute force before (maybe “count pairs with given sum” or “find the first duplicate”). Try to reframe it: what single piece of state could you update as you iterate? Share your before/after code in the comments—I’d love to see the quests you embark on! Happy hacking!