Kadane's Algorithm

The largest sum of any subarray

You get an array with positive and negative numbers. Find the subarray with the largest sum. (A subarray is a block of items that sit next to each other.) For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the answer is 6, from [4, -1, 2, 1]. Notice that this block includes a −1. Sometimes it is worth accepting a small loss to reach bigger gains later.

A sliding window does not work here (Lesson 23). With negative numbers, shrinking the window can make the sum bigger or smaller, so the window rules break. Kadane's algorithm solves the problem in one pass with a different idea. It is named after Jay Kadane, who found it.

Brute force: every start, every end

function maxSubArrayBrute(nums) {  let best = -Infinity;  for (let i = 0; i < nums.length; i++) {    let sum = 0;    for (let j = i; j < nums.length; j++) {      sum += nums[j];                    // sum of nums[i..j]      best = Math.max(best, sum);    }  }  return best;}console.log(maxSubArrayBrute([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

For each start, we keep a running sum as the end moves. This avoids an O(n³) solution (adding up every subarray from scratch). But it still costs O(n²) steps.

The key question: extend or start again?

Walk from left to right and keep one number called cur. It is the best sum of a subarray that ends exactly at the current index. For the next item x there are only two choices:

• Extend the best subarray ending at the previous index: cur + x.
• Start again with x alone: x.

Traced: Kadane on the classic example

1const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];▶let cur = nums[0];3let best = nums[0];4for (let i = 1; i < nums.length; i++) {5  cur = Math.max(nums[i], cur + nums[i]);6  best = Math.max(best, cur);7}8console.log(best);

It is important to start cur and best at nums[0], not at 0. Take an array where every number is negative, like [-3, -1, -2]. The answer is −1. If you start at 0, the code wrongly returns 0. This is also your first dynamic programming solution. Dynamic programming means you build the answer for each step from the answer for the previous step (Part 14).

Returning the subarray itself

Sometimes you must return the subarray itself, not just its sum. To do this, remember where the current run started. Whenever you find a new best sum, save that start position:

function maxSubArrayRange(nums) {  let cur = nums[0], best = nums[0];  let start = 0, bestStart = 0, bestEnd = 0;  for (let i = 1; i < nums.length; i++) {    if (nums[i] > cur + nums[i]) {       // starting again is better      cur = nums[i];      start = i;    } else {      cur += nums[i];    }    if (cur > best) {      best = cur;      bestStart = start;      bestEnd = i;    }  }  return { best, sub: nums.slice(bestStart, bestEnd + 1) };}console.log(maxSubArrayRange([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // { best: 6, sub: [ 4, -1, 2, 1 ] }

Best time to buy and sell stock

You get the price of a stock for each day. Buy on one day and sell on a later day, to make the largest profit. The same “best ending here” thinking works. If you sell today, the best you can do is to have bought at the cheapest price seen so far. Keep track of that lowest price as you walk through the prices.

function maxProfit(prices) {  let minPrice = Infinity, best = 0;  for (const p of prices) {    minPrice = Math.min(minPrice, p);        // cheapest day to buy so far    best = Math.max(best, p - minPrice);     // sell today?  }  return best;}console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5   buy at 1, sell at 6console.log(maxProfit([7, 6, 4, 3, 1]));    // 0   never profitable

This is Kadane's idea in another form. The profit from day i to day j equals the sum of the daily price changes between them. So the best trade is the maximum subarray of the list of daily changes.

Maximum product: track the minimum too

For the largest product, one number is not enough. A very negative product can become the largest positive product when you multiply it by another negative number. So keep two numbers: the largest product and the smallest product that end at the current index:

function maxProduct(nums) {  let hi = nums[0], lo = nums[0], best = nums[0];  for (let i = 1; i < nums.length; i++) {    const x = nums[i];    const candidates = [x, hi * x, lo * x];    hi = Math.max(...candidates);           // largest product ending here    lo = Math.min(...candidates);           // smallest (most negative) product ending here    best = Math.max(best, hi);  }  return best;}console.log(maxProduct([2, 3, -2, 4]));     // 6console.log(maxProduct([-2, 3, -4]));       // 24   the two negatives multiply

Circular subarrays

Now imagine the array is a circle, so a subarray may wrap from the end back to the start. A wrapping subarray is everything except a block in the middle. So the best wrapping sum is total − (the minimum subarray sum). Run Kadane for the maximum and for the minimum together. Then take the better of the two cases:

function maxSubarraySumCircular(nums) {  let total = 0;  let curMax = 0, bestMax = -Infinity;  let curMin = 0, bestMin = Infinity;  for (const x of nums) {    total += x;    curMax = Math.max(x, curMax + x);    bestMax = Math.max(bestMax, curMax);    curMin = Math.min(x, curMin + x);    bestMin = Math.min(bestMin, curMin);  }  if (bestMax < 0) return bestMax;           // all negative: the wrap trick would give 0  return Math.max(bestMax, total - bestMin);}console.log(maxSubarraySumCircular([5, -3, 5]));    // 10   wraps around: [5, 5]console.log(maxSubarraySumCircular([-3, -2, -3]));  // -2

There is one edge case. If every value is negative, the minimum subarray is the whole array. Then total − bestMin would be 0, which means an empty subarray, and that is not allowed. In this case, return the normal maximum.

Practice questions

For each question, first say what “the best answer that ends at index i” means. Then write the one-line update.

function maxSubArray(nums) {  let best = -Infinity;  for (let i = 0; i < nums.length; i++) {    let s = 0;    for (let j = i; j < nums.length; j++) best = Math.max(best, (s += nums[j]));  }  return best;}console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

function maxSubArray(nums) {  let cur = nums[0], best = nums[0];  for (let i = 1; i < nums.length; i++) {    cur = Math.max(nums[i], cur + nums[i]);    best = Math.max(best, cur);  }  return best;}console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6console.log(maxSubArray([1]));                             // 1console.log(maxSubArray([-3, -1, -2]));                    // -1

function maxProfit(prices) {  let best = 0;  for (let i = 0; i < prices.length; i++)    for (let j = i + 1; j < prices.length; j++)      best = Math.max(best, prices[j] - prices[i]);  return best;}console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5

function maxProfit(prices) {  let minPrice = Infinity, best = 0;  for (const p of prices) {    minPrice = Math.min(minPrice, p);    best = Math.max(best, p - minPrice);  }  return best;}console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5console.log(maxProfit([7, 6, 4, 3, 1]));    // 0

function maxProfit(prices) {  let profit = 0;  for (let i = 1; i < prices.length; i++) {    if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];  }  return profit;}console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 7console.log(maxProfit([1, 2, 3, 4, 5]));    // 4

function maxProduct(nums) {  let hi = nums[0], lo = nums[0], best = nums[0];  for (let i = 1; i < nums.length; i++) {    const x = nums[i];    const a = hi * x, b = lo * x;    hi = Math.max(x, a, b);    lo = Math.min(x, a, b);    best = Math.max(best, hi);  }  return best;}console.log(maxProduct([2, 3, -2, 4])); // 6console.log(maxProduct([-2, 0, -1]));   // 0console.log(maxProduct([-2, 3, -4]));   // 24

function maxSubarraySumCircular(nums) {  let total = 0, curMax = 0, bestMax = -Infinity, curMin = 0, bestMin = Infinity;  for (const x of nums) {    total += x;    curMax = Math.max(x, curMax + x);    bestMax = Math.max(bestMax, curMax);    curMin = Math.min(x, curMin + x);    bestMin = Math.min(bestMin, curMin);  }  return bestMax < 0 ? bestMax : Math.max(bestMax, total - bestMin);}console.log(maxSubarraySumCircular([1, -2, 3, -2])); // 3console.log(maxSubarraySumCircular([5, -3, 5]));     // 10console.log(maxSubarraySumCircular([-3, -2, -3]));   // -2

function maxAbsoluteSum(nums) {  let curMax = 0, curMin = 0, best = 0;  for (const x of nums) {    curMax = Math.max(x, curMax + x);    curMin = Math.min(x, curMin + x);    best = Math.max(best, curMax, -curMin);  }  return best;}console.log(maxAbsoluteSum([1, -3, 2, 3, -4]));     // 5console.log(maxAbsoluteSum([2, -5, 1, -4, 3, -2])); // 8

Make it stick

What's next

Lesson 25 finishes Part 4 with 2-D arrays. A 2-D array is a grid with rows and columns. You will transpose a matrix (swap its rows and columns), rotate it, read it in a spiral, and search a sorted matrix. These are all common interview questions.