Kadane's Algorithm & The Maximum Subarray Problem

A common interview question is -- given an array of integers, return the maximum sum of a subarray of the array. A 'subarray' is contiguous, and can include just one integer, or all of them. In this problem, you can assume that the array contains negative numbers--otherwise, the maximum subarray would just be the entire array. (You can find the Leetcode question here.)

For example, let's say you were given the input array of [2, 1, -2, 3, 2]. Subarrays include [2], [2, 1], [2, 1, -2], and so on. Just by looking at this array, you may be tempted to say that the maximum subarray sum is 5, taken by adding the last two elements. However, the maximum subarray is the entire array, which sums to equal 6.

A brute-force solution to this problem would be to compile every single subarray of an input, sum its elements, and return the highest number. That approach would take O(n^2) time--typically a sign that a more efficient method is possible.

In this blog post, I'll be walking through a solution to this problem that uses Kadane's Algorithm, and solves this problem in O(n) time. This post is based on a video made by CS Dojo here, and I definitely encourage people to check it out.

Kadane's Algorithm

In this approach, you're checking what the maximum subarray at each element is. Kadane's Algorithm says that the maximum subarray at each element is either the current element itself, or the current element plus the maximum subarray ending at the previous element.

Let's see how this would look on the example input. We can first start by initializing the current maximum to equal the first element, since there are no prior maximums to compare it against. We'll also initialize the global maximum to equal the first element for the same reason. So, the current maximum is 2, and the global maximum is 2.

Then, let's move on and check each next element, 1. According to Kadane, the largest sum is either the current element, or the sum of the current element and the previous largest sum. In this case, we're comparing 1, the current element, with 1+2, the sum of the current element and the previous largest sum. 3 is larger, so the current maximum becomes 3. Now, we have to check if the current maximum is greater than the previous maximum subarray, and if so, the current maximum becomes the global maximum. 3 is greater than 2, so 3 becomes the global maximum as well.

We then do that again for -2. When comparing -2 with 3 + (-2), we get that 1 is larger, so that becomes the current maximum. Because 1 is not larger than the global maximum, the global maximum remains unchanged.

Now we're onto element 3. The current maximum is either 3 or 3 + the previous current maximum, which is 1. That makes 4 the current maximum, and since 4 is greater than the existing global maximum, it's the new global maximum.

Finally, we're at the last element, 2. Kadane's Algorithm says that the maximum is either the element itself, or the element plus the previous current maximum (this shows why thinking [3,2] is the maximum subarray is not the right answer, as you may have thought by quickly looking at the array). In this case, we're comparing if 2 is greater than 2 + 4, or 6. 6 is greater, so that becomes the new current maximum. 6 is also greater than the previous global maximum, so it's the global maximum as well.

There are no more elements to check, so this algorithm would return 6 as the global maximum.

Kadane's Algorithm in JavaScript

To write this algorithm out, we need to store a couple of variables that hold current and global maximum. We also need to walk through through the array and perform checks on each element. Finally, we'll return the global maximum.

Let's start by initializing the current max and the global max, setting it equal to the first element in the input array. We do this because the first element has no prior elements to check against.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  //...
}

Next, starting with the element at index 1, and looping through the end of the input array, we'll perform checks on each element. To do this, we'll use a for loop.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    //...
  }
  //...
}

Now, we want to see whether the current element, nums[i] is greater than the sum of the current element and the sum of the previous subarray, maxCurrent + nums[i]. This is a good place to use Math.max(), which will return the larger of the values. Whichever one is larger will become the new maxCurrent.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    //...
  }
  //...
}

Now that we have the maximum subarray ending at the current element, we have to check if it's larger than the global max. If it is, it'll be the new global max.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    if (maxCurrent > maxGlobal) {
      maxGlobal = maxCurrent;
    }
  }
  //...
}

Once the for loop is finished, and all of the elements have been checked, we can return the global max.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    if (maxCurrent > maxGlobal) {
      maxGlobal = maxCurrent;
    }
  }
  return maxGlobal
}

And that's it! Let me know in the comments if you have any questions, or other approaches to this problem that you like.