Finds the contiguous subarray within a 1D numeric array that has the largest sum in a single O(n) pass and O(1) space.
Compact metadata for implementation and discovery.
Kadane's Algorithm solves the Maximum Subarray Problem in linear O(n) time using dynamic programming. At each index i, it decides whether to extend the best subarray ending at i - 1 or start a fresh subarray at i, tracking both the maximum sum and the [start, end] index boundaries.
Quick facts
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)
Interactive Runtime & Memory Budget Calculator
Estimate wall-clock latency, operation count, and working memory for Kadane's Algorithm across input scales.
428.6 µs
428.6 µs
128 B
dp[i] = \max(A[i],\; dp[i-1] + A[i])Best contiguous sum ending at index i.
Tested TypeScript and Python 3 implementations paired with unit tests covering edge cases, duplicate keys, and boundary conditions.
/**
* Kadane's Maximum Subarray — Single-pass O(n) maximum contiguous sum & span
* Time: O(n) | Space: O(1)
*/
export function kadaneMaxSubarray(values: readonly number[]): {
maxSum: number;
start: number;
end: number;
} {
if (values.length === 0) return { maxSum: 0, start: -1, end: -1 };
let maxSum = values[0], curSum = values[0];
let start = 0, end = 0, tempStart = 0;
for (let i = 1; i < values.length; i++) {
if (curSum + values[i] < values[i]) {
curSum = values[i];
tempStart = i;
} else {
curSum += values[i];
}
if (curSum > maxSum) {
maxSum = curSum;
start = tempStart;
end = i;
}
}
return { maxSum, start, end };
}Sliding contiguous window expanding when prefix gain is positive and resetting when prefix sum drops below zero.
Handles all-negative arrays cleanly by initializing maxSum and curSum to values[0] instead of 0.
What each reference supports for this entry.
Published Jay Kadane's linear-time maximum subarray algorithm.
Open sourceGood next jumps from the relationship graph, ranked for useful discovery.
Solves maximum subarray in O(n) time vs O(n log n) divide-and-conquer.