Kadane Algorithm explanation with implementation in C++

Kadane Algorithm is an efficient way to solve the maximum sub array problem.

So before we know about Kadane algorithm, first we shall look at that is the maximum sub array problem?

You will be given with an array, you need to find the continuous sub array whose sum is the largest sum.

Example, consider the following array:

[-1, 0, 2, 3, -2]

In the array above, you need to find a sub array with maximum sum.

By brute force we can see that sum of elements [2, 3] is 5. This is the maximum sum.

If you solve by brute force, it will take O(n) time at. This can be efficiently solved with help of Kadane’s algorithm.

Before going to kadane’s algorithm, we shall see how to solve by brute force approach:

At any index, we check what is the maximum sub array at that index:

So for our example,

[-1, 0, 2, 3, -2]

For the first index it is -1

For the second index it could be
max (
[-1 + 0],
[0]
)
Hence max = 0;

For the third index it could be
max (
[-1 + 0 + 2],
[0 + 2]
[2]
)
Hence max = 2;

For the forth index it could be
max (
[-1 + 0 + 2 + 3],
[0 + 2 + 3]
[ 2 + 3]
[3]
)
Hence max = 5;

Hence, the worst case in brute force approach is O(n^2).

By using kadane’s algorithm, we can reduce it to O(n) time.

1. The local maximum sub array is either the element at the current index

or

2. The current element combined with previous local maximum sub array.

We continue to calculate the above for all the elements in the array. After that we are going to pick the maximum sub array in the list of local_max_sub_array.

So how to do it programmatically?

Step 1: take 2 variables:
local_max_sub_array = a[0]
global_max_sub_array = a[0]

Step 2: Start a loop from index 1 to end of the array and perform below operation:
local_max_sub_array = max(arr[i], local_max_sub_array + arr[i])
global_max_sub_array = max (local_max_sub_array, global_max_sub_array)

Step 3:Return the global_max_sub_array.

Given array: [-1, 0, 2, 3, -2]

Initally 
local_max_sub_array = a[0] = -1
global_max_sub_array = a[0] = -1


Pass 1:
local_max_sub_array = max[arr[1], (-1 + arr[1])]
= max [0, -1] = 0

global_max_sub_array = max(0, -1) = 0


Pass 2:
local_max_sub_array = max[arr[2], (0 + arr[2])]
= max [2, 2] = 2

global_max_sub_array = max(0, 2) = 2


Pass 3:
local_max_sub_array = max[arr[3], (2 + arr[3])]
= max [0, 5] = 5

global_max_sub_array = max(3, 5) = 5


Pass 4:
local_max_sub_array = max[arr[4], (5 + arr[4])]
= max [-2, (5 - 2)] = 3

global_max_sub_array = max(3, 5) = 5

Hence the sum of maximum sub array is 5.

#include<stdio.h>

int kadane_algorithm(int a[], int size)
{
        int i;
        int max_sum_so_far=0;
        int max_ending_here = 0;
        
        for(i=0;i<size;i++)
        {
        	max_ending_here = max_ending_here + a[i];
        	
        	if(max_ending_here < 0)
        	{
        		max_ending_here =0;
			}
		    if(max_sum_so_far < max_ending_here)
		    {
			  
			  max_sum_so_far = max_ending_here;
			
			}
			
		}
return max_sum_so_far;
}


int main(){
	
	int i,size;
	
	printf("Enter the size of the array ");
	scanf("%d",&size);
	
	int a[size];
	printf("\n Enter the elements of the array");
	for(i=0; i<size; i++)
	{
		scanf("%d",&a[i]);		
	}
	 
	
	int max_sum = kadane_algorithm(a,size);
	
    printf("\n The Maximum Sum of the Sub Array is : %d",max_sum);
	
	
	return 0;
}

Enter the size of the array 5

 Enter the elements of the array-1
0
2
3
-2
 The Maximum Sum of the Sub Array is : 5

The time complexity of Kadane is O(n) time [linear time] in all the cases.

There is a sliding window approach to solve this problem. We shall see one variant of that algorithm in the next chapter.