Max Subarray Problem – Kadane’s Algorithm (Dynamic Programming)

Last modified date

Comments: 0

Problem

The max subarray problem is a problem where you have to find the contiguous subarray (containing at least one number) which has the largest sum, and return the sum.

The problem can be found here

Test Cases

InputOutput
[-2,1,-3,4,-1,2,1,-5,4]6

Solution

The way to solve this problem is use Kadane’s algorithm:

The way that this algorithm works is through dynamic programming.

We traverse the array and for each element perform the calculation to find the maximum value of either arr[i] and (arr[i] + localMax).

This works because for a given index if the value of the element at the index is greater than the sum of that element and the localMax, it is such that previous subarray elements do not contribute any increase in value to current max. So we don’t need the elements from the previous indexes to get a max subarray.

If the element at the current index is not greater than the sum of that element and the localMax then it means that in order to find the max subarray, we need the previous elements plus the current element.

Array IndexExplanationVariable Values
0So starting with the first element of the array, since it’s the first element at index 0, we don’t need to perform the calculation so the localMax and globalMax are both the element at index 0, which is -2.globalMax = -2
localMax = -2
1Then for index 1, arr[1] is the element 1, we perform the first calculation of finding the max value of arr[i] and (arr[i] + localMax).
The maximum value of 1 and (1 + -2 = -1) is 1.
So we set the localMax to 1 and since 1 is greater than the current globalMax, which is currently set to -2, we update the global max to 1 as well.
globalMax = 1
localMax = 1
2Then we move onto the index 2 which is the value -3.
So the max of -3 and (-3 + 1 = -2) is -2.
This means that previous elements in the array are still valuable to finding the max, so we update the localMax to -2.
We don’t change the globalMax.
globalMax = 1
localMax = -2
3Index 3 is the value 4.
The max of 4 and (4 + -2 = 2) is 4.
So we change the localMax to 4. Effectively we are saying that the previous elements are now irrelevant and we are restarting the subarray from index 3.
4 is greater than the current globalMax so we update it to the new value.
globalMax = 4
localMax = 4
4Index 4 is the value -1.
The max of -1 and (-1 + 4 = 3) is 3.
Update localMax to 3.
globalMax stays at 4.
globalMax = 4
localMax = 3
5Index 5 is the value 2.
The max of 2 and (2 + 3 = 5) is 5.
Update localMax to 5.
Update globalMax to 5.
globalMax = 5
localMax = 5
6Index 6 is the value 1.
The max of 1 and (1 + 5 = 6) is 6.
Update the localMax to 6.
Update the globalMax to 6.
globalMax = 6
localMax = 6
7Index 7 is the value -5.
The max of -5 and (-5 + 6 = 1) is 1.
Update localMax to 1.
globalMax stays at 6.
globalMax = 6
localMax = 1
8Index 8 is the value 4.
The max of 4 and (4 + 1) is 5.
Update localMax to 5.
globalMax stays at 6.
globalMax = 6
localMax = 5

So the answer for the given input is the value of the globalMax at the end which is 6.

And with this solution we scored the fastest ever time on Leet Code:

Runtime Complexity

Algorithm performs on linear time complexity O(n) as the array is only traversed once.

Space Complexity

Algorithm performs in constant space O(1)

See Also

If you liked this explanation, you might also like this interview question that was asked by Google.

JakTech

Leave a Reply

Your email address will not be published. Required fields are marked *

Post comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.