Kadane's algorithm finds the maximum-sum contiguous subarray in **O(n) time and O(1) space** replacing the obvious O(n²) brute force of trying every subarray.
The key insight: at each index, the best subarray ending here is either **just this element** or **the best subarray ending at i−1 plus this element**. Whichever is larger.
It's the textbook introductory example of dynamic programming on arrays every DP class teaches it, and it shows up in surprising disguises in real problems.
Typical Complexity Baseline
Metric
Value
Time
O(n)
Space
O(1)
See It
Concept Diagram
A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.
Kadane's algorithm running best subarray sum
If the running sum drops below the current value, restart the window from here.
Step 1/9Init at i=0. current = -2. best = -2.
Watch First
Video Explainer
A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.
Kadane's Algorithm to Maximum Sum Subarray Problem
The building blocks and terminology you need before everything else clicks. Skim or deep-read.
Running sum
What it is Best subarray sum ending at the current index. The DP state typically a single scalar.
Why it matters Running sum is a required building block for understanding how Kadane's Algorithm (Maximum Subarray) stays correct and performant on large inputs.
Best so far
What it is The maximum running sum seen across all indices visited. The answer.
Why it matters Best so far is a required building block for understanding how Kadane's Algorithm (Maximum Subarray) stays correct and performant on large inputs.
Restart decision
What it is At each index, choose: extend the running sum, or restart from this element. running = max(value, running + value).
Why it matters Restart decision is a required building block for understanding how Kadane's Algorithm (Maximum Subarray) stays correct and performant on large inputs.
Optional indexes
What it is Track start/end of the winning subarray by remembering when the running sum restarts.
Why it matters Optional indexes is a required building block for understanding how Kadane's Algorithm (Maximum Subarray) stays correct and performant on large inputs.
Contiguous subarray
What it is A range of consecutive indices [i..j]. Not the same as a subsequence (which can skip).
Why it matters A range of consecutive indices [i..j]. Not the same as a subsequence (which can skip). In Kadane's Algorithm (Maximum Subarray), this definition helps you reason about correctness and complexity when inputs scale.
DP state
What it is The minimal information needed to extend the solution. For Kadane: just the running sum at the previous index.
Why it matters The minimal information needed to extend the solution. For Kadane: just the running sum at the previous index. In Kadane's Algorithm (Maximum Subarray), this definition helps you reason about correctness and complexity when inputs scale.
Prefix sum reformulation
What it is Equivalent framing: max subarray sum = max over j of (prefix[j] − min prefix[i<j]). Same complexity, different mental model.
Why it matters Equivalent framing: max subarray sum = max over j of (prefix[j] − min prefix[i<j]). Same complexity, different mental model. In Kadane's Algorithm (Maximum Subarray), this definition helps you reason about correctness and complexity when inputs scale.
All-negative edge case
What it is When every element is negative, the answer is the largest single element. Handle by initializing running = best = arr[0], not 0.
Why it matters When every element is negative, the answer is the largest single element. Handle by initializing running = best = arr[0], not 0. In Kadane's Algorithm (Maximum Subarray), this definition helps you reason about correctness and complexity when inputs scale.
Walkthrough
Putting It All Together
Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.
Step 1/9
Init at i=0. current = -2. best = -2.
Step 2/9
i=1, value=1. 1 > -1 → reset window to i. current=1. best=1.
When this technique wins, when it loses, and what to reach for instead.
vs. Brute force O(n²)
Choose this when Always prefer Kadane O(n) vs O(n²) is a free win once you understand the algorithm.
Tradeoff None of practical significance. Brute force is only easier to explain in 30 seconds.
vs. Divide and conquer O(n log n)
Choose this when Kadane is faster (O(n)), simpler (no recursion), and uses constant space.
Tradeoff D&C generalizes more naturally to other problems; Kadane is a special-case shortcut.
vs. Prefix-sum + min-prefix tracking
Choose this when Kadane reads more directly. Prefix-sum is mathematically equivalent but adds an extra concept.
Tradeoff Prefix-sum framing extends naturally to 'subarray sum equals K' style problems; Kadane doesn't.
In Production
Real-World Stories
Where this shows up at real companies and what the on-call engineer learned the hard way.
Algorithmic trading prototypes
Single-position 'best buy/sell window' calculations in time-series price arrays are Kadane in disguise apply it to the array of daily price differences.
Takeaway Many 'best contiguous interval' problems in finance reduce to Kadane on a transformed array.
Game scoring engines
Scoring the best 'streak' in a sequence (e.g. cumulative score with positive/negative events) is direct Kadane find the highest contiguous run.
Takeaway Streak detection in event sequences is a textbook Kadane application.
Image processing max-energy region
2D image filters that find the max-energy connected band run Kadane along rows or columns after a column-pair compression the 2D max-submatrix problem.
Takeaway Kadane is the inner loop of the 2D extension; understanding 1D first makes 2D obvious.
Code
Implementation
A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.
Single linear pass. At each index, decide whether to extend or restart, and update best if the current running sum is a new max.
Complexity: Time O(n), Space O(1)
Kadane's algorithm with running and best sum
functionmaximumSubarraySum(values: number[]): number {
if (values.length === 0) {
thrownewError("Kadane requires at least one value.")
}
let runningSum = values[0]
let bestSumSoFar = values[0]
for (let valueIndex = 1; valueIndex < values.length; valueIndex += 1) {
const currentValue = values[valueIndex]
runningSum = Math.max(currentValue, runningSum + currentValue)
bestSumSoFar = Math.max(bestSumSoFar, runningSum)
}
return bestSumSoFar
}
Watch Out
Common Problems and Failure Modes
The bugs and edge cases that bite engineers most often. Skim before you ship.
Initializing best = 0 instead of best = arr[0]. Breaks on all-negative arrays you'd return 0 for an array like [-3,-1,-2].
Confusing subarray (contiguous) with subsequence (can skip). Kadane only solves contiguous.
Forgetting the empty-subarray decision: some problem statements allow returning 0 (empty subarray); others require ≥1 element. Read the prompt.
Trying to track start/end indexes naively they only update when the running sum restarts, not on every iteration.
Assuming Kadane works for max product. It doesn't products can flip sign, so you must track both running max **and** running min.
Pro Tips
Tips and Tricks
Small habits that pay off every time you reach for this pattern.
Start by writing the core invariant in one sentence before coding.
Test empty, single-item, and duplicate-heavy inputs early.
Pick the pattern first (map, pointers, recursion, heap, etc.), then implement details.
Track both time and space complexity while iterating on correctness.
Pattern Recognition
When to Use
Concrete signals that tell you this is the right pattern both at work and on LeetCode.
Real-system usage signals
Maximum-profit single-stock-trade problems (with allowable loss windows).
Maximum subarray sum, product, or any other associative metric over a contiguous window.
The 1D building block for the 2D 'max submatrix sum' problem (apply Kadane to every column-pair compression O(n³) total).
Detecting the most profitable / most lossy contiguous interval in time-series data.
Interview signal: 'find the best contiguous X' in a 1D array is almost always Kadane.