loading...
Cover image for Kadane's Algorithm & The Maximum Subarray Problem

Kadane's Algorithm & The Maximum Subarray Problem

alisabaj profile image Alisa Bajramovic Updated on ・5 min read

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.

Checking the first element, 2, and setting it equal to the current and global max

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.

Checking the second element, 1, and finding the current and global max

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.

Checking the third element, -2, and findign the current and global max

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.

Checking the fourth element, 3, and finding the current and global max

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.

Checking the final element, 2, and calculating the current and global max

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.

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

pic
Editor guide
 

I had a slight modification in this logic.
We can do without maxCurrent, coz if we encounter a -ve number it will always reduce the maxCurrent and a positive number will always increase it...
So we just keep modifying the current array with sum of all past elements as long as they are +ve... and not if -ve.
then we keep comparing maxGlobal with this sum.

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