Kadane's Algorithm & LeetCode 53 Maximum Subarray
Kadane’s Algorithm is used to obtain the maximum subarray sum, as seen in the Leetcode 53. Maximum Subarray:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array. Example: Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Brute-force Approach
Let’s take the example array:
[-2,1,-3,4,-1,2,1,-5,4]
We can solve the problem via brute-force but it goes as $O(n²)$:
def maxSubArray(self, nums: List[int]) -> int:
best_sum = 0
current_sum = 0
if len(nums)==1: return nums[0]
for i,x in enumerate(nums):
current_sum=x
for y in nums[i+1:]:
current_sum = current_sum + y
if current_sum>best_sum:
best_sum = current_sum
return best_sum
Basically, we calculate the following sums:
Fix the first value: -2 1.1: -2+1 = -1 <- best_sum 1.2: -2+1-3 = -4 1.3: -2+1-3+4 = 0 <- best_sum 1.4: -2+1-3+4-1 = -1 …. Fix the fourth value: 4 4.1: 4-1 = 3 4.2: 4-1+2 = 5 <- best_sum 4.3: 4-1+2+1 = 6 <- best_sum, this won’t change ….
About Kadane:
Joseph Kadane is a mathematician that provided this algorithm to solve the maximum subarray sum problem in $O(n)$ time complexity:
def maxSubarraySum(numbers: List[int]) -> int:
best_sum = nums[0]
current_sum = nums[0]
for x in nums[1:]:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
Easy? Not easy for me. Let’s dig deeper into why it works.
The full sum array: Fix the first value: -2
- $-2+1 = -1$ $\rightarrow$ The second value $1$ alone has a higher sum than $-2+1$, therefore we ditch the $-2$ and we begin counting from $1$ for a new subarray,
current_sum=1
,best_sum=1
- $1-3 = -2$ $\rightarrow$ The third value is lower than the sum with the previous
current_value
($-2>-3$), we continue a new subarray from last step.current_sum=-2
,best_sum=1
- $1-3+4 = 2$ $\rightarrow$ The 4th value updates the
current_value
to $4$ and thebest_value
to $4$. This resets the subarray we were adding because $4$ alone has a higher sum than $1-3+4$. - $4-1 = 1$ $\rightarrow$
current_sum=1
,best_sum=4
- $4-1 + 2 = 5$ $\rightarrow$
current_sum=5
,best_sum=5
- $4-1 + 2 + 1= 6$ $\rightarrow$
current_sum=6
,best_sum=6
, after thisbest_sum
won’t be updated again. - $4-1 + 2 + 1 -1 = 5$ $\rightarrow$
current_sum=5
,best_sum=6
- $4-1 + 2 + 1 -1 -5 = 0$ $\rightarrow$
current_sum=0
,best_sum=6
- $4-1 + 2 + 1 -1 -5 + 4 = 4$ $\rightarrow$
current_sum=4
,best_sum=6
If we had an extra number (less than 2), we would have to update the subarray we were adding.
In general, in line 6 of the Kadane implementation we decide to switch to another subarray, this happens in step 2 and 3. Meanwhile, line 7 keeps the highest sum we got so far.