Coders Packet

Kadane's Algorithm in C++

By Pratiti Prashant Pande

Kadane's Algorithm is an algorithm that helps in finding the largest sum of Contiguous subarray

In this module, we discuss an algorithm for finding the largest sum of adjacent elements which form a subarray of the given array. This is called Kadane's algorithm
So a subarray is an array within an array that has contiguous/adjacent elements
Let us take an example to understand this in a better way. Suppose we have an array {2, -3, 6, -4, 5}
The subarray could be {2}, {-3,6,-4}. The whole array could also be a subarray. The condition only is that the elements should be contiguous
The array {2,6,-4} is not valid since the elements are not contiguous(2 is not next to 6, there is 3 in between them)

So let us discuss what is exactly Kadane's algorithm
We will take two variables curr_sum to monitor the current sum and max_sum to monitor the maximum sum. We initialize both of these two variables to zero. Now since it is an array we will have to apply a for loop so that we cover the entire array and apply looping on each element only once

curr_sum=0, max_sum=0

2》Apply for loop
for(j=0; j< size of array; i++)
curr_sum= curr_sum +value_at_current_index
curr_sum=0                     //i.e. we will set the value of curr_sum=0 if the value comes out to be negative
if(max_sum<curr_sum)   //we update the value of max_sum at that point with curr_sum
max_sum= curr_sum

3》And finally we print the max_sum

To understand this algorithm let us manually work out and see how it works by considering an example
{2, -3, 6, -4, 5}
a[0] =2
a[0] =-3
a[0] =6
a[0] =-4
a[0] =5

curr_sum=0, max_sum=0
At i=0, a[0] =2
curr_sum=curr_sum + (2)
curr_sum=2 and max_sum=2

At i=1, a[1] = -3
curr_sum=curr_sum + (-3)
curr_sum=-1   So we will set curr_sum=0 since value is less than zero and max_sum will still remain 2

At i=2, a[2] =6
curr_sum=curr_sum + (6)
curr_sum=6   and now max_sum would be updated to 6, since max_sum< curr_sum

At i=3, a[3] =-4
curr_sum=curr_sum + (-4)
curr_sum=2 and max_sum will still remain 6

At i=4, a[4] =5
curr_sum=curr_sum + (5)
curr_sum=7 and max_sum=2
Now, max_sum is less than curr_sum. So max_sum would be updated and its value would be equal to 7
Hence, the Value of the largest Sum contiguous subarray for the given array is 7

Points to note:
• The algorithm used here will not work if all the elements in the array are negative
• Also, if all the elements that are entered are positive then the value of the Largest sum contiguous subarray would be the addition of all elements in the array
• The time complexity of Kadane's Algorithm is O(n)
• And it uses dynamic Programming

Sample output of the program

Download Complete Code


No comments yet