← Index

Techniques & Patterns

Kadane's Algorithm

Maximum sum of a contiguous subarray, in one O(n) pass.

What it is

At each position, decide whether extending the running subarray is better than abandoning it and starting fresh at the current element. Track the best 'ending here' sum and the best sum seen anywhere — one pass, no nested loops, no need to check every possible subarray.

Real-world examples

• Finding your best 7-day stretch of net-positive mood/spending/steps in a tracked log, without manually checking every possible date range.
• A stock trader scanning a price-change log for the best consecutive run of gains.

Where you've probably used this already

• 'Best time to buy and sell stock'-style problems — finding the most profitable contiguous window.
• Analytics dashboards surfacing 'your best streak' or 'strongest performing period' from a time series.
• Any 'find the best contiguous run' feature — best rolling conversion rate, best uptime streak, etc.

Complexity

Code

// Kadane's Algorithm — find the maximum sum of a CONTIGUOUS subarray,
// in O(n) with a single pass. The trick: at each position, decide
// whether extending the previous subarray is better than starting fresh.

function maxSubarraySum(nums) {
  let maxEndingHere = nums[0]; // best sum of a subarray ENDING at current index
  let maxSoFar = nums[0];      // best sum seen anywhere so far

  for (let i = 1; i < nums.length; i++) {
    // either extend the running subarray, or start a new one at nums[i]
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

// --- Variant that also returns which subarray produced the max ---
function maxSubarrayWithIndexes(nums) {
  let maxEndingHere = nums[0];
  let maxSoFar = nums[0];
  let start = 0;
  let bestStart = 0;
  let bestEnd = 0;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > maxEndingHere + nums[i]) {
      maxEndingHere = nums[i];
      start = i; // starting fresh here
    } else {
      maxEndingHere += nums[i];
    }

    if (maxEndingHere > maxSoFar) {
      maxSoFar = maxEndingHere;
      bestStart = start;
      bestEnd = i;
    }
  }
  return { sum: maxSoFar, subarray: nums.slice(bestStart, bestEnd + 1) };
}

// --- Example Usage ---
const data = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("maxSubarraySum:", maxSubarraySum(data)); // 6
console.log("maxSubarrayWithIndexes:", maxSubarrayWithIndexes(data));
// { sum: 6, subarray: [4, -1, 2, 1] }

// Real uses of this exact shape:
// - "best N-day window to buy/sell" style stock profit problems
// - finding the best-performing rolling period in analytics data
//   (best 7-day streak of net-positive signups, etc.)