Kadane's algorithm

Overview

Kadane's algorithm finds the maximum sum of a contiguous subarray in O(n) time and O(1) space. At each index it asks one question: is it better to extend the best subarray ending at the previous index, or to start fresh at this element?

It is the simplest example of dynamic programming on arrays: best ending here = max(nums[i], best ending before + nums[i]). Your repo's thumb rule captures it well: when you need one global best over all subarrays, think Kadane.

When to use it

• Maximum (or minimum) sum of a contiguous subarray.
• Values can be negative (otherwise the whole array is the answer).
• The answer depends on the best subarray ending at each position.
• Variants: maximum product, circular arrays, best stock profit.

Problem patterns it solves

Where it is used in real software

Key terms

current

The best sum of a subarray that ends exactly at index i.

best

The best sum seen at any index so far (global answer).

Restart

When current + nums[i] < nums[i], begin a new subarray at i.

Optimal substructure

The best subarray ending at i extends the best ending at i - 1 or starts at i.

How it works, step by step

1. 1
   Initialize with the first element

   current = best = nums[0]. Do not use 0, or an all-negative array returns the wrong answer.

2. 2
   For each next element

   current = max(nums[i], current + nums[i]).

3. 3
   Update the global best

   best = max(best, current).

4. 4
   Track indexes if needed

   When you restart, record start = i; when best improves, record the start and end.

Trace of current and best

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The maximum subarray sum is 6. A negative running sum can never help a future subarray, which is the whole insight behind restarting.

Implementation

1function maxSubArray(nums) {2  let current = nums[0];3  let best = nums[0];4  for (let i = 1; i < nums.length; i++) {5    current = Math.max(nums[i], current + nums[i]);6    best = Math.max(best, current);7  }8  return best;9}10 11// Return the subarray boundaries too12function maxSubArrayRange(nums) {13  let current = nums[0], best = nums[0];14  let start = 0, bestStart = 0, bestEnd = 0;15  for (let i = 1; i < nums.length; i++) {16    if (nums[i] > current + nums[i]) {17      current = nums[i];18      start = i;19    } else {20      current += nums[i];21    }22    if (current > best) {23      best = current;24      bestStart = start;25      bestEnd = i;26    }27  }28  return { best, bestStart, bestEnd };29}30 31// 918. Circular: max(normal Kadane, total - min subarray)32function maxSubarraySumCircular(nums) {33  let total = 0;34  let curMax = 0, bestMax = -Infinity;35  let curMin = 0, bestMin = Infinity;36  for (const x of nums) {37    curMax = Math.max(x, curMax + x);38    bestMax = Math.max(bestMax, curMax);39    curMin = Math.min(x, curMin + x);40    bestMin = Math.min(bestMin, curMin);41    total += x;42  }43  return bestMax < 0 ? bestMax : Math.max(bestMax, total - bestMin); // all negative44}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Initializing best = 0.

  Fix: Start with nums[0] so an all-negative array returns its largest element.

• Circular variant when all numbers are negative.

  Fix: total - min would give 0 (empty subarray); return bestMax instead.

• Maximum product without tracking the minimum.

  Fix: A large negative times a negative becomes a large positive.

Interview questions

Practice problems