Kadane's Algorithm
Find the contiguous subarray with the largest sum in O(n).
How it works
Kadane's Algorithm solves the maximum subarray problem in a single linear pass, making it one of the most elegant examples of dynamic programming at its simplest. The key insight is a local decision made at every index: is it better to extend the current running subarray, or to abandon it and restart fresh from the current element? If the accumulated sum so far is negative, it can only hurt the future total — so we discard it. This greedy choice is provably optimal, and no information about future elements is ever needed.
The algorithm maintains two invariants across the scan. The first is the current subarray: the best contiguous run ending exactly at the current index. The second is the global best: the best current subarray seen anywhere in the array so far. At every step the current subarray is updated first, then the global best is updated if the current surpasses it. Because both updates are O(1), the overall complexity is O(n) time and O(1) space — a significant improvement over the O(n²) brute-force approach of checking all pairs of start and end indices.
Kadane's Algorithm handles arrays with mixed positive and negative numbers naturally. The only edge case is an all-negative array, where the maximum subarray is the single least-negative element; the formulation used here — initializing bestSum to -∞ — handles this correctly by always keeping at least one element. Variants of the algorithm can also track start and end indices (as this implementation does), return the actual subarray, handle circular arrays, or be extended to 2D for maximum-sum submatrix problems.
Complexity
Visualizer
Where it's used in the real world
Algorithmic trading platforms
Maximum profit window detection in stock price time seriesFinancial systems model daily price changes as a signed array (positive = gain, negative = loss). Kadane's Algorithm finds the optimal contiguous buy-hold-sell window in O(n), enabling real-time scanning of thousands of tickers without the O(n²) cost of checking every entry/exit pair.
Signal processing pipelines (audio/radio)
Maximum energy segment detection in sampled waveformsIn radar, sonar, and audio analysis, engineers search for the contiguous time window with the highest signal-to-noise energy. Representing samples as signed amplitudes and applying Kadane's Algorithm identifies burst-energy segments in real time, replacing expensive sliding-window convolutions.
Computer vision / image processing
Maximum brightness region in a 1D pixel row or histogramThe 2D variant of Kadane's Algorithm (applied column-by-column after compressing rows) is the standard approach for finding the maximum-sum submatrix in a grayscale image. This powers region-of-interest detection, blob analysis, and exposure-correction heatmaps in OpenCV pipelines.
Implementation
function kadane(array: number[]): { sum: number; start: number; end: number } {
let currentSum = 0;
let currentStart = 0;
let bestSum = -Infinity;
let bestStart = 0;
let bestEnd = 0;
for (let i = 0; i < array.length; i++) {
if (currentSum + array[i] > array[i]) {
currentSum += array[i];
} else {
currentStart = i;
currentSum = array[i];
}
if (currentSum > bestSum) {
bestSum = currentSum;
bestStart = currentStart;
bestEnd = i;
}
}
return { sum: bestSum, start: bestStart, end: bestEnd };
}
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const result = kadane(arr);
console.log(result); // { sum: 6, start: 3, end: 6 }
console.log(arr.slice(result.start, result.end + 1)); // [4, -1, 2, 1]