Pattern Guide
Kadane's Algorithm & Subarray Variants
"Max subarray sum in O(n). Circular variant, k disjoint subarrays, submatrix."
Kadane's algorithm finds the maximum subarray sum in O(n). Key variants: (1) circular array — subtract min subarray from total; (2) at most k elements; (3) k disjoint non-overlapping subarrays; (4) maximum sum submatrix. All share the core insight of maintaining a running "best" and "current" state as we scan.
Problems you can solve with this pattern
4 problems · click any to start solving
// Classic Kadane's
function maxSubarray(nums) {
let maxSum = -Infinity, cur = 0;
for (const n of nums) {
cur = Math.max(n, cur + n);
maxSum = Math.max(maxSum, cur);
}
return maxSum;
}
// Circular variant: total - minSubarray OR maxSubarray (handle all-negative)
function maxCircular(nums) {
const total = nums.reduce((a, b) => a + b, 0);
let maxSum = -Infinity, minSum = Infinity, curMax = 0, curMin = 0;
for (const n of nums) {
curMax = Math.max(n, curMax + n); maxSum = Math.max(maxSum, curMax);
curMin = Math.min(n, curMin + n); minSum = Math.min(minSum, curMin);
}
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}
// Maximum submatrix sum: fix top row r1, extend to bottom r2, apply Kadane to column sums
function maxSubmatrix(matrix) {
const m = matrix.length, n = matrix[0].length;
let ans = -Infinity;
for (let r1 = 0; r1 < m; r1++) {
const colSum = new Array(n).fill(0);
for (let r2 = r1; r2 < m; r2++) {
for (let c = 0; c < n; c++) colSum[c] += matrix[r2][c];
ans = Math.max(ans, maxSubarray(colSum));
}
}
return ans;
}Kadane's classic: scan left to right, maintaining current_sum (extend or restart) and max_sum. For circular arrays: max of (max linear subarray) and (total sum - min linear subarray). The min subarray covers elements NOT in the circular maximum subarray. For k disjoint subarrays: DP with k states. For submatrix: fix top and bottom rows, apply Kadane to column sums.
// Classic Kadane's
function maxSubarray(nums) {
let maxSum = -Infinity, cur = 0;
for (const n of nums) {
cur = Math.max(n, cur + n);
maxSum = Math.max(maxSum, cur);
}
return maxSum;
}
// Circular variant: total - minSubarray OR maxSubarray (handle all-negative)
function maxCircular(nums) {
const total = nums.reduce((a, b) => a + b, 0);
let maxSum = -Infinity, minSum = Infinity, curMax = 0, curMin = 0;
for (const n of nums) {
curMax = Math.max(n, curMax + n); maxSum = Math.max(maxSum, curMax);
curMin = Math.min(n, curMin + n); minSum = Math.min(minSum, curMin);
}
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}
// Maximum submatrix sum: fix top row r1, extend to bottom r2, apply Kadane to column sums
function maxSubmatrix(matrix) {
const m = matrix.length, n = matrix[0].length;
let ans = -Infinity;
for (let r1 = 0; r1 < m; r1++) {
const colSum = new Array(n).fill(0);
for (let r2 = r1; r2 < m; r2++) {
for (let c = 0; c < n; c++) colSum[c] += matrix[r2][c];
ans = Math.max(ans, maxSubarray(colSum));
}
}
return ans;
}- Classic max subarray: O(n) with restart-or-extend
- Circular: max(linear, total - linear_min), exclude all-negative case
- Submatrix max sum: fix two rows, Kadane on column prefix sums, O(m²n)
- Max ≤ k: sorted set of prefix sums, O(mn² log m)
- k disjoint subarrays: DP with k states, O(nk)
Classic pitfall: Circular formula gives 0 when all elements negative (total - total = 0 is wrong). Check if maxSum > 0 first.