Coders Packet

Kadane's Algorithm for circular Subarray in C++.

By Garvit Jethwani

In this packet we are implementing a C++ Program for updating the use of Kadane's Algorithm for the Maximum Circular Subarray Problem.

For finding the Maximum sum of the subarray, if we use the brute force approach of finding the sum of every subarray and then return the maximum of that then it would take O(N3) time. So in that case Kadane's Algorithm comes handy, which would do the same in O(N) time and O(1) space complexity.

Kadane's Algorithm - First we initialize the two variables in the array with Best_Max_Ending and Best_Max_Sofar with the first element of the array, after which we start the loop from the second element of the array. 

We find the maximum contiguous subarray up to that index. For which we would assign the Best_Max_Ending = max(Best_Max_Ending+Array[i], Array[i]) meaning that either the max would be after extending the previous subarray sum or start again from that element. And Best_Max_Sofar would be the maximum of all that updations. Returning the Best_Max_Sofar after the loop termination.

 

But Kadane's Algorithm would not work independently in the case of the Circular subarray.

There are two cases that arise for this problem. 1st case would be Non_wrapping in which the max subarray is not circular. 2nd case would be Wrapping in which the max subarray would be circular. And We would return the max of Non_wrapping_sum and Wrapping_sum.

Algorithm -

Non_Wrapping_Sum would be directly given by the Kadane algorithm.

But For Wrapping_Sum we would remove the Non-Contributing elements from the sum(Removing the most negative which would not contribute in the max subarray)

Array[i] = -Array[i] for non-contributing elements sum. 

Max_Subarray_Sum = Total Sum of Array - Sum of Non-Contributing Elements.

The program will return the maximum of  Non_wrapping and Wrapping Sum.

Download project

Reviews Report

Submitted by Garvit Jethwani (Gjgarvit)

Download packets of source code on Coders Packet