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

1. $-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
2. $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
3. $1-3+4 = 2$ $\rightarrow$ The 4th value updates the current_value to $4$ and the best_value to $4$. This resets the subarray we were adding because $4$ alone has a higher sum than $1-3+4$.
4. $4-1 = 1$ $\rightarrow$ current_sum=1, best_sum=4
5. $4-1 + 2 = 5$ $\rightarrow$ current_sum=5, best_sum=5
6. $4-1 + 2 + 1= 6$ $\rightarrow$ current_sum=6, best_sum=6, after this best_sum won’t be updated again.
7. $4-1 + 2 + 1 -1 = 5$ $\rightarrow$ current_sum=5, best_sum=6
8. $4-1 + 2 + 1 -1 -5 = 0$ $\rightarrow$ current_sum=0, best_sum=6
9. $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.