Computer Science
Kadane’s Algorithm — In plain English
Let’s understand Kadane’s algorithm which is an elegant way of solving the maximum subarray problem. Before looking at Kadane’s algorithm, let me first introduce the “maximum subarray problem”
Maximum Subarray Problem
We are given an array of numbers, we have to find a contiguous subarray in it which has the maximum possible sum amongst all possible subarrays of this array. For e.g., here’s an array:
2, -3, 7, 5, -1, -6, 7, 4, 2, 3
Let’s look at a few subarrays of this array. One of the subarrays is [7, 4, 2 ,3] which has a sum of 7 + 4 + 2 + 3 = 16. But does it have the maximum sum amongst all the possible subarrays? How about [7, 5, -1, -6, 7, 4, 2, 3] ? This has a sum of 7+5 -1 -6 + 7 + 4 + 2 + 3 = 21. Is it the one? Likely, but we are not yet 100% sure.
Brute Force Approach
One guaranteed way to find out the best solution, is to find out at all possible subarrays of the input array, calculate the sum of each subarray and find out the maximum amongst them. This can be done as follows:
class Solution {
public int maxSubArray(int[] nums) { //Assuming -1_000_01 <= nums[i] <= 1_000_01
int max = -1_000_01;
for(int i = 0; i < nums.length; i++) {
for(int j = i; j < nums.length; j++) {
int sum = sum(i, j, nums);
max = Math.max(max, sum);
}
}
return max;
}
private int sum(int s, int e, int[] arr) {
int sum = 0;
for(int i = s; i <= e; i++) {
sum = sum + arr[i];
}
return sum;
}
}
As can be seen, we have 2 nested for-loops for computing the subarrays and then within it, there’s a call to the ‘sum’ function for calculating the array sum which itself has a for-loop for iterating over the subarray. So overall, we have 3 nested for-loops. For an array consisting of ’n’ elements, this results in a time complexity of O(n³)! This surely isn’t going to scale for large values of ’n’. Can we do better?
Kadane’s Algorithm
Kadane’s algorithm is an optimal approach for solving the maximum subarray problem. In order to understand the problem, let’s adopt a metaphor of days of our life, where on some days you are happy 😊 (denoted by smiley faces) while on some other days you may be 😔 (denoted by sad faces). On some very happy days, you may have a lot of 😊😊😊 and on some really bad days, you may have a lot of 😔😔😔.
Now with this metaphor in place, we can define a singular purpose in our life, which is, maximize our happiness and minimize sadness. In order to achieve this, we adopt a very simple philosophy in life — Do not carry baggage from the past unless it makes you happy. Let’s see how we can put this in practice.
We translate our input array into this metaphor as follows — Negative values are represented as sad faces and positives as smiley faces.
Now each entry in the input array can be thought of as a day in our life and the value in it could be interpreted as the happy or sad faces depending on whether it is a positive or negative value. And with each passing day, we keep a running total of the happy or sad faces from the previous days and compare it with the present day. And while doing so, we stay true to our philosophy of not carrying over any past sadness. Basically what this means is that if my past’s running total depletes my today’s extent of happiness, I just discard it and start afresh from today. Something as illustrated below:
Starting from day 1, we choose whatever we have on that day. In the above illustration, it is 😊😊. Now on day 2, we have a previous running sum of +2 which is worth retaining (it is net positive) and hence we add it to day 2. Basically 😊😊 + 😔😔😔 = 😔. If we had not retained the previous days running sum, we would have been worse off at 😔😔😔. So we made a good choice. We continue with this approach for each day. It is interesting to see what we do on day 3. On day 3, we have a past running balance of -1 i.e. 😔. It is no use keeping it as it decreases our happiness. So we discard it and start afresh on day 3 with +7, basically 😊😊😊😊😊😊😊 .
Now as we proceed through the days, we should also keep track of the happiest day (the day with the maximum sum of smileys). That is simple enough, we just keep updating the maximum happiness attained on any given day if it’s more on that particular day compared to any of the days in the past. In the above illustration, it happens on day 10 when the total sum = +21. And guess what? This is also the maximum subarray sum of the provided input array, which was our main objective at the outset of this discussion.
Let’s take a look at the programmatic implementation of this approach:
class Solution {
public int maxSubArray(int[] nums) { //Assuming -1_000_01 <= nums[i] <= 1_000_01
int max = -1_000_01;
int sum = -1_000_01;
for(int num : nums) {
sum = Math.max(sum + num, num);
max = Math.max(max, sum);
}
return max;
}
}
As can be seen above, we just need to go through the list elements once and always choose the larger of the “current element” and the “current element + previous sum”. And we also need to keep track of the “maximum” value seen so far. Ultimately when we have gone through the whole array once, this maximum value would contain the maximum possible sum of a subarray in the input list. And that’s it!
In terms of time complexity, it is O(n) as we need to go over the array once. And in terms of space complexity, we just need to keep track of a couple of variables (the running sum and the maximum) and hence constant O(1). Overall this is a huge gain when compared to the brute force approach which had O(n³) time complexity.
I hope that now you have a solid understanding of Kadane’s algorithm after going through this article.
If algorithms pique your interest, you may also want to read some of my other articles on Kahn’s algorithm for topological sorting and Boyer Moore’s Voting Algorithm. Thanks!
