In this article, we will learn how to find the maximum subarray sum using Kadane’s Algorithm. So, given an array, we need to find the maximum sum of a subarray. Consider the following example.

A = [3, -1, 4, 1, -5]
MSS = 7
The contiguous array elements having the largest sum are 3, -1, 4, and 1. Therefore, the maximum subarray is [3, -1, 4, 1], and its sum (MSS) is 7.

One straightforward approach to solve the above problem is to apply the brute force technique, i.e., check all the possible combinations. We calculate the sum of each possible subarray and then take its maximum.

More specifically, we do the following:

For every index i, we find all the subarrays starting with the element at that index and calculate their sums. We take the maximum of these sums. Let’s call it the current maximum sum at the index i, i.e., currMaxi.

Once we have calculated the currMax for every index, we take the maximum of these values, which results in the global sum, i.e., the maximum subarray sum.

Use Kadane’s Algorithm to Find the Maximum Subarray Sum

Let’s take the above same array and find the maximum subarray sum using this approach. Moreover, we will start in the backward direction as it will be helpful later.

As you can observe, this is a computationally expensive approach with the time complexity of O(n2), where n is the length of the array.

An efficient solution to solve this problem is to apply Kadane’s Algorithm. The algorithm says that if we know the current maximum sum at the index i, we can calculate the current maximum sum at index i+1 using that and the element at the index i+1. Mathematically,

currMaxi+1 = max(arr[i+1], currMaxi + arr[i+1])

Here, arr[i+1] contains the element at index i+1.

Consider subarrays for indices 3 and 2 in the above figure. As you can see, if you add 1 (element at index 3) to every subarray for index 2 plus adding an extra subarray containing only one element (element at index 3), we will get the subarrays for index 3. In other words, adding 1 to subarrays sum for index 2 results into the sum of subarrays for index 3. Following that, we can say that the current maximum sum at index 3 will either be the current maximum sum at index 2 plus 1 or just 1, i.e.,

currMaxi+1 = max(Arr[i+1], currMaxi + Arr[i+1])
Here, i = 2
currMax3 = max(1, 6 + 1) = max(1, 7) = 7

Similarly, you can try for other array indices and get a better understanding of the algorithm.

Note that currMax0 is equal to the element at index 0 since there are no elements before it.

Kadane’s Algorithm is a dynamic programming algorithm. In dynamic programming, a problem gets divided into sub-problems. Moreover, each sub-problem gets calculated only once by storing the result of that sub-problem when it is first encountered.

Implementation of Kadane’s Algorithm

def mssKadane(arr):
  result =  [] #array to store the current maximum at each index currMaxi
  currMax = 0
  for num in arr:
    currMax = max(num, currMax+num)
    result.append(currMax)
  mss = max(result)
  return mss

arr = [3, -1, 4, 1, -5]
mss = mssKadane(arr)
print(f"The MSS of array {arr} is: {mss}")

Output

The MSS of array [3, -1, 4, 1, -5] is: 7

In the above implementation, we create a result array in which we add the current maximum sum at each index. We calculate currMax at each index using Kadane’s Algorithm. Then, we take the maximum of the result array to get the MSS. This approach has a time and space complexity of O(n). The O(n) space complexity is because of the creation of the result array. The good thing is that it can be reduced to O(1). Instead of storing each currMax, we create a variable mss with quite a small initial value such as -infinity. At each iteration, we compare currMax with mss. If it is greater, we update the mss variable. In this way, mss will have the maximum of all the current maximum sums. Consider the updated implementation with O(n) time complexity and O(1) space complexity.

import math
def mssKadane(arr):
  mss = -math.inf
  currMax = 0
  for num in arr:
    currMax = max(num, currMax+num)
    if currMax > mss:
      mss = currMax
  return mss

arr = [3, -1, 4, 1, -5]
mss = mssKadane(arr)
print(f"The MSS of array {arr} is: {mss}")

Output

The MSS of array [3, -1, 4, 1, -5] is: 7