Pattern Reference
Kadane's Algorithm Variants
"Maximum subarray sum in O(n), with circular, 2D, and product variants."
Loading...
Deep Dive Tutorial
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.
Kadane's variants
// 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;
}Worked Problems
chart-column
Kadane variants cheat sheet:
- 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.
- 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.