paint-brush
Kadane’s Algorithm Explained with Examplesby@mithratalluri
57,707 reads
57,707 reads

Kadane’s Algorithm Explained with Examples

by Mithra TalluriDecember 13th, 2020
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow
EN

Too Long; Didn't Read

Given an array, the algorithm to find the maximum subarray sum is called Kadane’s Algorithm. It can be applied to a 1D array or 2D matrix. The algorithm can be of any dimension. 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. We have two choices: either start at the current index or add the current element to the maximum of 0 and previous sum.
featured image - Kadane’s Algorithm Explained with Examples
Mithra Talluri HackerNoon profile picture


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! 😃