Maximum Subarray: Kadane's Algorithm
Tags: competitiveprogamming, kadanealgorithm, maximumsubarray, dynamicprogramming
Published: 2023-05-02 11:27:41

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.

1.  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.

2. 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?"

3. 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()
}

```