📈 Kadane's Algorithm

One-line summary: Find the maximum-sum contiguous subarray in O(n) by tracking the best sum ending at each position.

---

Concept

At each index decide: extend the previous subarray, or start fresh?

maxEndHere = max(arr[i], maxEndHere + arr[i])
maxSoFar   = max(maxSoFar, maxEndHere)

---

Diagram

---

Time & Space Complexity

Variant	Time	Space
Max subarray sum	O(n)	O(1)
Circular max subarray	O(n)	O(1)

---

Common Patterns

Basic Kadane

function maxSubarraySum(arr) {
  let maxEndHere = arr[0],
    maxSoFar = arr[0];
  for (let i = 1; i < arr.length; i++) {
    maxEndHere = Math.max(arr[i], maxEndHere + arr[i]);
    maxSoFar = Math.max(maxSoFar, maxEndHere);
  }
  return maxSoFar;
}

Circular Variant

function maxCircular(arr) {
  const total = arr.reduce((s, x) => s + x, 0);
  const maxLinear = kadane(arr);
  const minLinear = kadane(arr.map((x) => -x));
  const maxCircular = total + minLinear;
  return maxCircular === 0 ? maxLinear : Math.max(maxLinear, maxCircular);
}

---

Pitfalls

• All-negative array: result is the largest single element, not 0
• Circular variant: if all elements are negative the circular answer is 0 — guard against it

---

Practice Problems

Problem	Difficulty	Solution
LC 53 — Maximum Subarray	Medium	View Solution
LC 918 — Maximum Sum Circular Subarray	Medium
LC 152 — Maximum Product Subarray	Medium
LC 1749 — Maximum Absolute Sum of Any Subarray	Medium
LC 238 — Product of Array Except Self	Medium
CC — Maximum Subarray Sum (KCON)	Medium
LC 643 — Maximum Average Subarray I	Easy
LC 325 — Maximum Size Subarray Sum Equals k	Medium
LC 1567 — Maximum Length of Subarray With Positive Product	Medium
LC 1856 — Maximum Subarray Min-Product	Medium
LC 1186 — Maximum Subarray Sum with One Deletion	Medium
LC 121 — Best Time to Buy and Sell Stock	Easy
LC 122 — Best Time to Buy and Sell Stock II	Medium
LC 697 — Degree of an Array	Easy
LC 978 — Longest Turbulent Subarray	Medium
LC 1004 — Max Consecutive Ones III	Medium
LC 1191 — K-Concatenation Maximum Sum	Medium
LC 1395 — Count Number of Teams	Medium
LC 1524 — Number of Sub-arrays With Odd Sum	Medium
LC 1546 — Maximum Number of Non-Overlapping Subarrays	Medium
CC — Chef and Subarrays (CHEFSUM)	Medium
CC — Maximum Subarray (MAXSUM)	Easy
CC — Subarray with Given Sum (SUBSUM)	Medium

---

Related Topics

• Prefix Sum — complementary single-pass technique
• Dynamic Programming — Kadane is a 1D DP solved greedily
• Sliding Window — for bounded subarray variants

← Back to Home · © sparshjaswal