sko.kr
  • Home
  • Blog
  • Algorithms - 0. Kadane's Algorithm

Algorithms - 0. Kadane's Algorithm

algorithmsdynamic-programmingarraysoptimizationkadane
By sko•9/27/2025•4 min read

When to use Kadane's Algorithm

Use Kadane's when you need to find the optimal contiguous subarray based on some cumulative property. While most commonly used for maximum sum, it can be adapted for:

  • Maximum sum (classic use case)
  • Maximum product (with modification for handling negatives/zeros)
  • Longest subarray with specific properties (e.g., sum equals k)
  • Minimum sum (by negating values or reversing comparison)
  • Any problem where you can make a local decision to extend or restart based on cumulative state

Example problem

Stock Trading: Given daily stock price changes [-2, 1, -3, 4, -1, 2, 1, -5, 4], find the best consecutive period to hold the stock.

  • Day 0: Lost $2
  • Day 1: Gained $1
  • Day 2: Lost $3
  • ...and so on

Answer: Hold from Day 3 to Day 6 (the subarray [4, -1, 2, 1]) for a total gain of $6.

Single most important insight

Every subarray must end somewhere - and at each position, we make the optimal local decision (extend vs restart) that guarantees finding the global maximum by checking all possible endings with their best starts.

Mental note: The algorithm's genius lies in focusing on "best subarray ending at index i". At each position, we only need to decide: "Should I add the current element to the best subarray ending at the previous index, or start fresh?" This simple decision automatically explores all possible subarrays.

Decision Framework

At every element, you face one simple decision:

  • Extend the current subarray (add to what you have)
  • Restart with a fresh subarray (abandon the past)

Code

function kadanes(nums: number[]) {
  let globalMax = nums[0];
  let localMax = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const currentNum = nums[i];
    // Decision framework
    const extendSubarray = localMax + currentNum;
    const startNewSubarray = currentNum;
    localMax = Math.max(startNewSubarray, extendSubarray);

    globalMax = Math.max(globalMax, localMax);
  }

  return globalMax;
}

Doubt buster

Common doubt: "The algorithm only considers extending or restarting at each position. What if dropping just the first few elements of the current subarray would give a larger sum?"

This is a sophisticated concern about Kadane's algorithm. Let's address it with concrete examples.

Why you might think it could miss better subarrays

Consider array [-2, 3, 5, -1, 6]. When tracking subarrays, you might think:

  • "At position 4, we have subarray [3, 5, -1, 6] with sum 13"
  • "But what if we had a subarray like [-2, 3, 5, -1, 6] and wanted to drop just the -2?"
  • "The algorithm seems to only add to the end or restart completely - can't we drop from the beginning?"

Why this thinking is wrong

Key realization: Every possible "partial drop" was already considered at earlier positions!

Let's trace [-2, 3, 5, -1, 6] to see how Kadane handles this:

Position 0: localMax = -2  ([-2])
Position 1: localMax = 3   ([3])         → Compared: -2+3=1 vs 3, chose 3 (dropped -2!)
Position 2: localMax = 8   ([3, 5])      → Compared: 3+5=8 vs 5, chose 8
Position 3: localMax = 7   ([3, 5, -1])  → Compared: 8+(-1)=7 vs -1, chose 7
Position 4: localMax = 13  ([3, 5, -1, 6]) → Compared: 7+6=13 vs 6, chose 13

The magic moment: At position 1, when we chose to restart with 3 instead of extending to get 1, we automatically dropped the -2! The algorithm already considered and made the optimal choice.

Concrete example: All drop possibilities are covered

Think about any subarray you might want - let's say you're worried about missing [5, -1, 6] (dropping both -2 and 3):

  • Dropping first element [-2]: Already considered at position 1 when we restarted
  • Dropping first two elements [-2, 3]: Already considered at position 2 when we compared restart (5) vs extend (8)
  • Dropping first three elements [-2, 3, 5]: Already considered at position 3 when we compared restart (-1) vs extend (7)

Every possible starting point for a subarray ending at position 4 was already evaluated when we computed the best subarray ending at each earlier position!

Why local decisions guarantee we check everything

The brilliance of Kadane's algorithm is that "restart" doesn't just mean starting fresh - it means:

  • "Everything before this point would make my sum worse"
  • "All possible subarrays that include earlier elements have already been evaluated"
  • "By dropping everything, I'm making the optimal choice"

When we extend, we're saying "keeping everything from my optimal start point is still beneficial." When we restart, we're saying "drop it all - even the best subarray ending here before this point would make things worse."

The guarantee: Since every subarray must end somewhere, and we find the optimal start for each possible ending position, we've implicitly checked every possible subarray - including all the ones where we drop various elements from the beginning!

← Back to Blog