Maximum Subarray with Kadane’s Algorithm

Maximum Subarray Sum problem

This is a famous problem which is (probably no more considered as a hard problem itself, but) a useful tool to solve many harder ones. It’s great (and probably a must) to have in your problem solving toolkit. Basically, it asks you to find the contiguous subarray which has the maximum sum. Once understood, you will be able to tweak the solution to find minimum as well.

Below is the Leetcode version of this classic problem.

The Problem in Leetcode

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Source: Leetcode 53. Maximum Subarray

Solution – Naive approach

As you can guess, the easiest solution is to run two nested for loops through the array, take sum for each inner loop and save the maximum sum somewhere. This is no brainer with a runtime complexity of O(n²).

We won’t waste time with this approach. It will be a good exercise for you to code it up if you have time and interest. If not, let’s jump into the better approach! 🙂

Solution – Better approach with Kadane’s Algorithm

Joseph “Jay” Born Kadane (born January 10, 1941) is the Leonard J. Savage University Professor of Statistics, Emeritus in the Department of Statistics and Social and Decision Sciences at Carnegie Mellon University. Kadane is one of the early proponents of Bayesian statistics, particularly the subjective Bayesian philosophy.

wikipedia

Professor Kadane, made his great contribution to gift us an algorithm solving this classic problem. This algorithm is named Kadane’s Algorithm, (most probably) to honour his contribution.

The algorithm is simple. It goes through the array and takes cumulative sum and updates a variable which keeps the max sum with the cumulative sum. If at some point the cumulative sum is negative, it makes the cumulative sum equals 0.

It’s hard to visualize why it works. Let’s see three scenarios about how and why this algorithm works. Among these threes, the second one is more important to understand.

We classified the scenarios as,

1. When all values if the array are positive
2. When there is a mixed type values (positive + negative)
3. When all values are negative

All values are positive

Imagine we have an array nums as below. We also have a variable sum_so_far to take the cumulative sum and a variable max_sum to keep the maximum sum as the name suggests.

If we simply update sum_so_far, we should be able to have the maximum sum when we reach at the end of this positive array. Because, since all values are positive, there is no chance of our sum_so_far to decrease at any point. It will only increase as it passes through and in the end, it will hold the maximum sum! (which will eventually update max_sum)

If it’s still not understood, please see the images below. Here is the first step (i = 0).

Then, i points to 1 as below:

Then, i points to 2 as below:

Finally, i points to 3 as below:

So far so good? If not, please reread and think about it a bit more 🙂 If good, let’s see the more complex scenario below.

Positive + Negative

The more complex situation arises when an array has both positive and negative values. In fact, this can lead sum_so_far to be negative! How do we deal with negative values? (Numbers are probably same as people. It’s not easy to deal with negative people as well!)

Let’s imagine we have a new array nums as below.

Let’s start our algorithm the we did before. At i = 0, we have sum_so_far = 6 and max_sum has been updated to 6. So far so good.

At i = 1, we have a negative value. But it’s not that negative that can make our sum_so_far negative! However, now we have sum_so_far = 6 – 4 = 2 and max_sum has no change. Again, so far so good.

At i = 2, we have sum_so_far = 5 and max_sum has no change. Let’s move forward, shall we?

At i = 3, we have sum_so_far = 7 and max_sum has been updated to a new value 7!

Now is the fun part when we are at i = 4. We found a huge negative value (-9) which is strong enough to make our sum_so_far to be negative (-2). What we have gained so far, will be destroyed by this single negative value. But we can’t let that happen. So, we forcefully reinitialize our sum_so_far = 0.

Thankfully, we saved our achievements so far in the max_sum variable. If our sum_so_far never becomes positive again and have no hope to cross the current max_sum value, then current max_sum will be the answer.

At i = 5, we found 8 and our sum_so_far = 0 + 8 = 8. See, if we didn’t re-initialized sum_so_far = 0 in the previous step, we would not have make it 8 now! With that, our max_sum is updated to 8 now. 🙂

So, you see, the magic of this algorithm is to reinitialize sum_so_far when it becomes negative.

But, why does it work?

See the below image where sum_so_far is represented by a bar of blue boxes. The straight line indicates its ups and downs. See the straight line starts at 0 (when sum_so_far = 0). For each new additional array element, we see the ups and downs of the straight line. When it goes to negative, there is no point of taking negative values into account. Because, it will down the straight line even further and we will not get the maximum value. We will only go towards downward and sum_so_far will just decrease and decrease.

That’s why, we reinitialize sum_so_far = 0 to have a new fresh start! 🙂

(Not sure if it explains the solution. If not, please comment which part is not clear to you 🙁 )

All negative

Now, let’s understand why this solution also works for arrays with all negative values.

Before moving on, let’s say we have an array with all negative values as below. Now, think about it. If all values are negative, is there any need to add even two values together? If we add two negative values, it will make the sum more negative, right? If we add three negative values, again even more negative will be the sum.

So, for arrays with all negative values, we need to check each values independently and the maximum value among all will be the final answer.

But our sum_so_far is only adding up values, right? How we will each values independently? Remember, we are re-initializing sum_so_far = 0 for each time it becomes negative. Since all values are negative here, it means, we will have to re-initializing sum_so_far = 0 each time which will in other words give us ability to check each values independently. Smart enough, Right? Thanks to Mr. Kadane! 🙂

Let’s see the process in action below. At i = 0, sum_so_far = 0 + (-6) = -6 and our max_sum is updated to -6 now. Since sum_so_far < 0, we make sum_so_far = 0.

When we made sum_so_far = 0 and we add the next value, there is no effect of the previous value. That’s how this algorithm also deals each values independently!

This is what happens at i = 1.

And for i = 2

And finally for i = 3

Code

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int sum_so_far = 0;
        int len = nums.size();
        int max_sum = INT_MIN;
        for(int i = 0; i < len; i++){
            sum_so_far += nums[i];
            max_sum = max(sum_so_far, max_sum);
            if(sum_so_far < 0) sum_so_far = 0;
        }
        return max_sum;
    }
};

Conclusion

Hope you enjoyed this post. This was relatively a larger post. We are not sure if we could make the solution clear or made you more confused! :/

Please write to us your feedback in the comment box. We really need to know your comments for better posts in future. Thank you and …

Happy coding! 😀