From Zero to Hero: Mastering Kadane's Algorithm — Like Leveling Up in *The Legend of Zelda*

The Quest Begins (The "Why")

Ever stared at a coding interview question that asked for the maximum sum of a contiguous subarray and felt like you were staring at a locked chest with no key? I remember my first encounter with LeetCode 53 — I wrote a double‑loop, checked every possible slice, and watched my solution sputter out with a time‑limit exceeded error. The frustration was real; it felt like trying to defeat Ganon with a wooden sword. I knew there had to be a smarter way, something that didn’t make me re‑examine the same numbers over and over again. That moment — when brute force gave up and my brain started whispering “there’s a pattern here” — was the spark that sent me on the quest for a DP hero’s tool.

The Revelation (The Insight)

The breakthrough came when I stopped thinking about all subarrays and started asking a simpler question: what’s the best subarray that ends right at the current element?

If I know the answer for position i‑1, extending it to i is just a matter of deciding whether to keep the previous segment or start fresh at i. In other words:

maxEndingHere[i] = max(nums[i], maxEndingHere[i‑1] + nums[i])

Why does this work? Because any optimal subarray ending at i either:

1. Consists solely of numsi, or
2. Takes the optimal subarray ending at i‑1 and appends numsi.

There’s no third option — any longer segment would have to include one of those two cases as its suffix. So we never need to look back farther than the immediate previous state. That’s the optimal substructure property at the heart of dynamic programming, and it collapses the problem from O(n²) to a single linear pass. The global answer is just the maximum of all maxEndingHere values we encounter.

It felt like discovering the hidden warp pipe in Super Mario Bros. — one tiny shortcut that skips an entire level of grunt work.

Wielding the Power (Code & Examples)

The Struggle (Before) Brute‑Force – O(n²)

function maxSubarrayBrute(nums) {
  let best = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum > best) best = sum;
    }
  }
  return best;
}

Every pair (i, j) is examined — fine for tiny inputs, but it chokes on anything beyond a few hundred elements.

(After) Kadane’s Algorithm – O(n)

function maxSubarrayKadane(nums) {
  let maxEndingHere = nums[0];
  let maxSoFar      = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Either start new at nums[i] or extend the previous segment
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    // Keep the best we've seen overall
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

Why this is O(n): The loop touches each element exactly once, doing only constant‑time work per iteration. No nested loops, no recursion depth — just a straightforward scan.

Common Traps (the “bosses” to avoid)

1. Forgetting the negative‑all case – If you initialize maxEndingHere to 0, an array like [-2, -3, -1] would incorrectly return 0. Start with the first element so the algorithm respects the requirement to pick at least one number.
2. Updating maxSoFar before maxEndingHere – You need the current segment’s best before you compare it to the global best; otherwise you might miss a segment that ends at the current index.

Interview‑style variants

• Best Time to Buy and Sell Stock (LeetCode 121) – Treat daily price differences as the array; the max subarray sum equals the max profit. Same Kadane logic, O(n) time, O(1) space.
• Maximum Subarray Sum with One Deletion – A slight twist where you keep two states: one with no deletion, one with one deletion. Still linear, still built on the same “extend or restart” intuition.

Why This New Power Matters

Mastering Kadane’s isn’t just about solving one LeetCode problem; it’s a lens for spotting any situation where you need the best contiguous chunk — whether you’re optimizing revenue over time, finding the most volatile period in a signal, or even chaining gameplay bonuses in a game dev project. Once you see the pattern, you start reframing problems: “What’s the best ending here?” becomes a go‑to question, and solutions flow like a well‑timed combo move in a fighting game.

The best part? The algorithm is tiny enough to type out in an interview under pressure, yet powerful enough to impress interviewers who watch you turn a seemingly quadratic nightmare into a graceful linear sweep.

Your Turn – The Next Quest

Grab a piece of paper (or your IDE) and try this: given an array of integers, find the maximum sum of a subarray whose length is at least L (a common twist). Hint: you’ll still want a running window, but you’ll need to remember the best prefix sum up to i‑L. How would you adapt Kadane’s core idea to handle the length constraint?

If you crack it, drop your solution in the comments — let’s see who can level up first! 🚀