Kadane's Algorithm

Tags

Kadane's Algorithm

Category

Famous Algorithms

Difficulty

Medium

Problem Statement

Given a non-empty array of integers, find the maximum sum of any contiguous subarray. A subarray must contain at least one element.

Intuition

At each position in the array, the maximum subarray ending here either extends the previous maximum subarray or starts fresh from the current element. If the running sum becomes negative, it is better to discard it and start a new subarray at the current element. We track the global maximum across all positions.

Approach

  1. Initialize maxEndingHere to the first element and maxSoFar to the first element.
  2. For each element from index 1 onward:
    • maxEndingHere = max(element, maxEndingHere + element) — either start a new subarray at this element or extend the previous one.
    • maxSoFar = max(maxSoFar, maxEndingHere) — update the global maximum.
  3. Return maxSoFar.

Pseudocode

function kadanesAlgorithm(array):
    maxEndingHere = array[0]
    maxSoFar = array[0]

    for i from 1 to length(array) - 1:
        maxEndingHere = max(array[i], maxEndingHere + array[i])
        maxSoFar = max(maxSoFar, maxEndingHere)

    return maxSoFar

Time & Space Complexity

  • Time: O(n) where n is the length of the array. Single pass.
  • Space: O(1) — only two variables are maintained.

Key Insights

  • The decision at each element is binary: extend or restart. This greedy choice leads to the globally optimal solution.
  • Kadane's algorithm is a special case of dynamic programming where dp[i] = maximum subarray sum ending at index i, and we only need dp[i-1] to compute dp[i].
  • The algorithm handles negative numbers correctly. If all numbers are negative, the result is the largest (least negative) single element.
  • To also track the subarray boundaries (start and end indices), update index variables whenever a new subarray starts or the global max is updated.

Edge Cases

  • Single-element array: return that element.
  • All positive numbers: the maximum subarray is the entire array.
  • All negative numbers: the maximum subarray is the single largest (least negative) element.
  • Array with all zeros: return 0.
  • Mix of positive and negative numbers where the optimal subarray is in the middle.
  • Large arrays with alternating positive and negative values.

Linked mentions