Maximum Subarray: Kadane's Algorithm

Balaji R — Tue, 02 May 2023 11:27:41 +0000

Hey there, folks! Today we're going to talk about Kadane's algorithm, a nifty little trick for finding the maximum subarray sum in an array. If you're a fan of dynamic programming, you're going to love this one.

Kadane's Algorithm Explained

So, how does it work? Well, it's pretty simple, actually.

We start by initializing two variables: maxSoFar and maxEndingHere. maxSoFar keeps track of the maximum subarray sum we've seen so far, and maxEndingHere keeps track of the maximum subarray sum that ends at the current position in the array.
Then, we loop over the array and do a little dance. For each element in the array, we update maxEndingHere to be the maximum of the current element and the sum of the previous maxEndingHere and the current element.

In other words, we're asking ourselves: "is it better to start a new subarray at this element, or to add this element to the subarray that ended at the previous element?"
Once we've updated maxEndingHere, we compare it to maxSoFar _and update _maxSoFar if maxEndingHere is greater. This means that we've found a new maximum subarray sum.

And that's it! Once we've looped over the entire array, we return maxSoFar and pat ourselves on the back for a job well done.

Let's take a look at an example to see how it all fits together. We'll start with this array:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

We start by setting maxSoFar and maxEndingHere to -2, which is the first element of the array. Then we loop over the rest of the array and do our little dance:

For the second element (1), we update maxEndingHere to be the maximum of 1 and -2 + 1, which is 1.
For the third element (-3), we update maxEndingHere to be the maximum of -3 and 1 - 3, which is -2.
For the fourth element (4), we update maxEndingHere to be the maximum of 4 and -2 + 4, which is 4.
And so on.

At the end of the loop, maxSoFar is 6, which is the maximum subarray sum in the array. Pretty cool, huh?

Now, you might be wondering: "What if the array has only negative numbers?" Well, fear not, my friend! Kadane's algorithm can handle that too. Let's take a look at this array:

nums = [-5, -2, -3, -1, -4]

We start by setting maxSoFar and maxEndingHere to -5, which is the first element of the array. Then we loop over the rest of the array and do our little dance:

For the second element (-2), we update maxEndingHere to be the maximum of -2 and -5 - 2, which is -2.
For the third element (-3), we update maxEndingHere to be the maximum of -3 and -2 - 3, which is -3.
And so on At the end of the loop, maxSoFar is -1, which is the maximum

Kotlin Implementation of the algorithm:

fun maxSubArray(nums: IntArray): IntArray {
    var maxSoFar = nums[0]
    var maxEndingHere = nums[0]
    var start = 0
    var end = 0
    var newStart = 0
    for (i in 1 until nums.size) {
        if (nums[i] > maxEndingHere + nums[i]) {
            newStart = i
            maxEndingHere = nums[i]
        } else {
            maxEndingHere += nums[i]
        }
        if (maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere
            start = newStart
            end = i
        }
    }
    return nums.slice(start..end).toIntArray()
}

DEV Community: Balaji R

Maximum Subarray: Kadane's Algorithm

Kadane's Algorithm Explained

Kotlin Implementation of the algorithm: