Kadane’s Algorithm Explained

Given an array, the algorithm to find the maximum subarray sum is called Kadane’s Algorithm.The array can be of any dimension. For simplicity, let’s start with a 1D array.

Let’s take a 0-indexed array:

arr: [5, 7, -3, 2, 9, 6, 16, 22, 21, 29, -14, 10, 12]

We can start the subarray at any point. Let’s say we start at index 2 i.e., arr[2] = -3. Now, at index 3, the sum will be -3 + 2 = -1. If we started the subarray at index 3 instead, the sum at index 3 is 2, which is greater than the previous sum.

So we have two choices: either start at the current index or add the current element to the previous sum.

And since we want the maximum subarray sum, we add the current element to the maximum of 0 and previous sum (zero here denotes that we’re starting anew from the current element).

This problem falls under Dynamic Programming Paradigm.

Let’s take an array dp[] where each dp[i] denotes maximum subarray sum ending at index i (including i).

We can say that

Base conditions: dp[0] = arr[0]

Answer:A maximum element in the dp[] array

Time Complexity: O(N)Space Complexity: O(N)

We could optimize the space complexity by taking dp[i-1] which is the previous sum into a variable, eliminating the need for dp[] array.

Time Complexity: O(N)Space Complexity: O(1)

We could also find the indices of the subarray having the maximum sum.

We could apply Kadane’s to 2D matrix as well, where we have to find the maximum submatrix sum. Feel free to try out kadane’s for 2D matrices. Thank you for reading! 😃

Kadane’s Algorithm Explained was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.