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

Blog Hero