Kadane’s Algorithm


We are given an array of n integers. We have to find the maximum non-empty contiguous subarray sum.


Naive Approach :

· We will check for every possible subarray and find the sum of that subarray.

· From all the subarrays possible we will take that sum which is maximum among them.


Code :

Time Complexity :

  • We are using two nested loops.

· Clearly, total number of operations done = n + (n-1) + …. + 1

= n*(n+1)/2

So, the time complexity is O(n2)


Efficient solution using Kadane’s Algorithm:

Approach :

· Let dp[i] denotes the maximum sum subarray ending at ith index.

· Now, we will have only two possibilities :

(i) That subarray contains only 1 element ,i.e, value at ith index

(ii) That subarray will contain the value at ith index + maximum subarray ending at (i-1)th index.

· Therefore, our recursive condition will be :

dp[i] = max(dp[i-1] + a[i], a[i]) , a is the array of given integers

  • Base Case : dp[0] = a[0]

· Now we need to find the maximum value among the dp array.


Code :

Time Complexity : O(n)


Applications :

Finding the maximum sum subarray by flipping the sign of a subarray, atmost once.

Approach :

· It’s obvious that we need to find the minimum sum subarray and then flip its sign.

· For finding the minimum sum subarray in O(n) time we can use Kadane’s algorithm. Method will be just the reverse of the described method.


Note : If the minimum sum subarray is greater than 0, then there is no need to change the sign because if we change then our value will decrease from the already given array sum.

Practice Problems :

https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0
https://www.codechef.com/problems/CDVNT01F
https://www.codechef.com/problems/KOL15B


Happy Coding 😊

By Programmers Army

Contributed by Shubham Kumar