Kadane's Algorithm

Maximum contiguous subarray sum in O(n) time using linear DP.

[Dynamic Programming]|

Jul 9, 2026

|explanatory_notes.md|

#kadane#maximum-subarray#dp#linear

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll kadane(const vector<ll> &arr) {
    ll best = 0, cur = 0;
    for (ll x : arr) {
        cur = max(x, cur + x);
        best = max(best, cur);
    }
    return best;
}

12 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Kadane's Algorithm

Finds the maximum sum of a contiguous subarray in $O(n)$ .

Recurrence

Let $dp[i]$ = maximum subarray sum ending at index $i$ :

dp[i] = \max(a[i],\; dp[i-1] + a[i])

a[i]

: start a new subarray here

dp[i-1] + a[i]

: extend the previous subarray

The answer is $\max_{0 \le i < n} dp[i]$ .

Notes

This version returns 0 for all-negative arrays (empty subarray allowed). To require at least one element, initialize both variables to arr[0] and loop from index 1

Space-optimized: only two variables instead of a full DP array

When to Use

Maximum subarray sum

Maximum sum submatrix (apply Kadane per column-compressed row)

As a subroutine in divide-and-conquer or 2D problems

Complexity

Time —

O(n)

Space —

O(1)