Introduction
SPOILER ALERT: This section is specifically dedicated to bragging about Kadane, not the algorithm. So, feel free to skip this section. (No, I am kidding! I'd actually prefer that you read it...)
Joseph "Jay" Born Kadane (whose full name I just gathered from Wikipedia) is the scientist who published this algorithm I am going to talk about. I am nothing but in awe for this man. It's been a year since I've known this algorithm, but whenever I think of this algo, I can't help but feel immense respect and look up to him. This algorithm is so simple once you understand it but that wouldn't degrade any of its charisma. Instead, (I do and suppose that) you will feel a sense of accomplishment and the warmth in your chest. That's the effect of brilliant logic that even novices like us can implement—it touches the heart! (In a modest claim, we're not novices; we're outstanding. Or perhaps outstanding novices...) With the "irrelevant" part out of the way, let's delve into the essence.
Explanation
Problem statement: You need to find the sum of the subarray having maximum sum among all subarrays of given integer array.
The Algo:
- The problem statement mentions "integer array". Which means negative integers included. We obviously don't want to add a negative integer to get maximum sum... but it has a downside -
Say the array has elements - 7 1 -4 5
If you're stopping at 7+1 = 8, you have a sub-optimal solution.
Because 7+1-4+5 = 9
- So instead, we'll stop adding when the sum becomes -ve. This does not have any downsides. Because whatever sum lies ahead of this point, is better off without this negative sum decreasing its value.
- But we're not sure if a sum that's calculated up until this point will be greater or the sum that's yet to be calculated newly, somewhere beyond this point.
- Therefore, we maintain a maxSum variable that would, at a given instance of time, store the maximum sum calculated since the start, up until then.
I hope you're not confused. If you are, take a look at this code and read those lines again.
Algorithm
maxSum,sum <- (-infinity)
loop {
sum <- sum + ele
maxSum <- Maximum(sum, maxSum)
if (sum < 0) {
sum = 0
}
}
return maxSum
NOTE: In every iteration, maxSum is updated not caring whether the sum is -ve or not. It might strike you as a redundancy. After all, (sum > maxSum) is possible only when sum>0. But think about an array with all -ve integers- because the sum is always -ve, the maxSum never gets updated from (-infinity) to the least negative integer. There are other cases too. So, it's important to try to update maxSum in each iteration.
Returning Subarray
- Where is the fun in returning just the maxSum?? Let's return the subarray that produces the maxSum!!
- Don't feel overwhelmed! All we have to do is figure out the start and the end of the subarray.
- So, while calculating a sum, we obviously need to know where it started. For this, we'll have a 'startIndex' variable. But we don't actually need the endIndex because we're not sure if the current sum is going to be the maxSum. Instead, we'll have 'actualStart', 'actualEnd' variables indicating the start and end indices of the sum which is in maxSum variable.
- Whenever maxSum variable is (actually) updated, current startIndex will be actualStart and current index will be actualEnd.
maxSum,sum <- (-infinity)
startIndex, actualStart <- 0
loop {
sum <- sum + ele
if (sum > maxSum) {
maxSum <- sum
actualStart <- startIndex
actualEnd <- current_index
}
if (sum < 0) {
sum = 0
startIndex = current_index
}
}
return array[actualStart..actualEnd]
Conclusion
Kadane's Algorithm is a brilliant example of how simple logic can solve complex problems efficiently. By understanding and implementing this algorithm, you can find the maximum subarray sum in linear time. Give it a try (in your favorite programming language), I am sure you'll ace it!!
P.S.: Did you know that Kadane's Algorithm is an iterative dynamic programming algorithm? I've never seen a simpler DP algorithm than this!
SOCIAL SHARE CARD GENERATOR