Kadane’s Algorithm: Maximum Subarray Sum
Kadane’s algorithm is commonly used to solve maximum subarray sum problem. Using two variables to store the maximum subarray sum ending at each index and the maximum subarray sum we have encountered so far respectively. The beauty of it is only one pass is required to find the largest possible subarray sum.
Table of Contents· How Does Kadane’s Algorithm Work?
· Graphical Explanation
· Code Implementation
∘ Complexity
∘ Golang
∘ Python
How Does Kadane’s Algorithm Work?
Kadane’s Algorithm is usually applied to solve the maximum subarray sum problem. The idea of this algorithm is to traverse the entire array and define two variables to store the max subarray sum we have encountered so far(global max) and the max subarray sum ending at each index(local max).
There are two possibilities to get the local max.
- take the max subarray sum ending at the previous index and add the number at the current index.
- just take the number at the current index because the previous maximum subarray sum is negative.
local max at index i
= max(local max at index i-1 + array[i], array[i])Update the global max if the value of local max is greater than the global max.
global max at index i
= max(global max at index i - 1, local max at index i)Kadane’s algorithm is a dynamic Programming approach because it deducts the maximum subarray sum ending at the current index according to the previous maximum subarray sum.
Graphical Explanation
two variables:
1. localMax: the maximum subarray sum ending at index i
2. globalMax: the maximum subarray sum we have seen so farformulas:
localMax = max(localMax + array[i], array[i])
globalMax = max(globalMax, localMax)
Code Implementation
Complexity
Time: O(n)
Space: O(1)
n: the total number of elements in the given array
