Kadane's Algorithm

Kadane’s Algorithm is a dynamic programming approach that finds the maximum sum of a contiguous subarray in linear time

Real-World Analogy

Imagine you are driving through multiple cities, and each city gives you a certain amount of money (some might even charge you). Your goal is to find the longest continuous stretch of cities where you end up with the most money.

• Without Kadane: You would try every possible combination of cities. That’s checking every start point and every end point, which is expensive.
• With Kadane: As you drive from city to city, you keep two things in mind:
  1. Current balance: How much money you have if you started from your last restart point
  2. Best balance ever: The maximum money you’ve had at any point during the trip

At each city, you ask yourself: “Is it better to add this city to my current stretch, or should I start fresh from here?” If continuing gives more money, keep going. If starting fresh is better, reset your current balance. This way, you only need to drive through once.

Visual Explanation

Let’s visualize how Kadane’s algorithm processes the array [-2, 1, -3, 4, -1, 2, 1, -5, 4] step by step.

  graph LR
    subgraph Input
        N0[-2]
        N1[1]
        N2[-3]
        N3[4]
        N4[-1]
        N5[2]
        N6[1]
        N7[-5]
        N8[4]
    end

    subgraph Decision
        D1{Extend or Restart?}
        D2{Extend or Restart?}
        D3{Extend or Restart?}
        D4{Extend or Restart?}
        D5{Extend or Restart?}
        D6{Extend or Restart?}
        D7{Extend or Restart?}
        D8{Extend or Restart?}
    end

    subgraph Results
        L0["localMax: -2<br>globalMax: -2"]
        L1["localMax: 1<br>globalMax: 1"]
        L2["localMax: -2<br>globalMax: 1"]
        L3["localMax: 4<br>globalMax: 4"]
        L4["localMax: 3<br>globalMax: 4"]
        L5["localMax: 5<br>globalMax: 5"]
        L6["localMax: 6<br>globalMax: 6"]
        L7["localMax: 1<br>globalMax: 6"]
        L8["localMax: 5<br>globalMax: 6"]
    end

    N0 --> D1 --> L1
    L0 --> D1

    N1 --> D2 --> L2
    L1 --> D2

    N2 --> D3 --> L3
    L2 --> D3

    N3 --> D4 --> L4
    L3 --> D4

    N4 --> D5 --> L5
    L4 --> D5

    N5 --> D6 --> L6
    L5 --> D6

    N6 --> D7 --> L7
    L6 --> D7

    N7 --> D8 --> L8
    L7 --> D8

    style L6 fill:#aaf,stroke:#333,stroke-width:2px

Key Observations:

• At index 0, both local and global are -2 (only option)
• At index 1, we restart because 1 > -2 + 1 (local becomes 1)
• At index 6, we achieve our maximum of 6 (subarray [4, -1, 2, 1])
• We never need to track more than the current position

When to Use Kadane’s Algorithm

Use this pattern when you see these characteristics:

• You need to find the maximum or minimum sum of a contiguous subarray
• Input contains both positive and negative numbers
• Problem asks for “maximum profit,” “best time to buy/sell,” or similar optimization
• Need to optimize
  O(N^2)
  brute force to
  O(N)
• Want
  O(1)
  space complexity (no extra storage)
• Problem involves circular arrays (wrap-around behavior)

Complexity Analysis

Derivation:

• Time: Each element is processed exactly once. We only do constant-time comparisons and assignments per element.
• Space: We store only 2 to 4 integer variables regardless of input size. The input array itself is not modified.

Common Mistakes

1. Wrong Initialization: Starting localMax and globalMax at 0 instead of the first element. This fails for all-negative arrays.
2. Forgetting All-Negative Case: When all numbers are negative, the maximum sum should be the largest (least negative) element, not 0.
3. Circular Array Logic: Forgetting the edge case where the minimum subarray equals the total sum (all negative), which breaks the wrap-around formula.
4. Empty Array Handling: Not checking for empty input before accessing the first element.
5. Returning Wrong Value: Returning localMax instead of globalMax at the end.

Next Steps

Ready to implement? Check out our Code Templates for memorizable blueprints in 6 programming languages, or jump directly to Practice Problems to apply Kadane’s algorithm to real LeetCode questions.