Kadane’s Algorithm

(Dynamic Programming)

Wondering why Kadane’s Algorithm is used?

You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum

This can be done using,

1. Brute Force Approach

Time Complexity : O(nlogn)

Auxiliary Space : O(1)

• We iterate through array elements twice using two for loops in order to find the maximum subarray sum.

2. Kadane’s Algorithm

Time Complexity : O(n)

Auxiliary Space : O(1)

We use dynamic programming here, it is a lot about optimization.

Algorithm —

Assume our array to be arr[].

1. Initialize :

curr_sum = 0 (It will store the maximum so far in an array)

max_sum = INT_MIN

1. Run a LOOP

i) curr_sum = curr_sum + arr[i];

ii) if our curr_sum is less that zero, then curr_sum = 0

iii) else max_sum = max(max_sum, curr_sum);

At the end, return max_sum

Let’s say this is our array,

On running the loop,

We assigned 0 to curr_sum because curr_sum < 0.

and so on……

Code Walkthrough

#include<iostream>
#include<climits>
using namespace std;
int kadanesalgo(int a[], int n)
{
 int curr_sum=0;
 int max_sum=INT_MIN;
 for(int i=0;i<n;i++)
 {
  curr_sum = curr_sum+a[i];
  if(curr_sum<0)
   curr_sum=0;
  else
   max_sum = max(curr_sum, max_sum);
 }
 return max_sum;
}
int main()
{
 int n, arr[50];
 cin>>n;
 for(int i=0;i<n;i++)
  cin>>arr[i];
 int max_sum = kadanesalgo(arr,n);
 cout<<"\nMaximum subarray sum : "<<max_sum;
}