Maximum Sum Circular Subarray

Given an circular array of integers, find subarray in it which has the largest sum.

 

For example,


Input:  {2, 1, -5, 4, -3, 1, -3, 4, -1}
Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.
 

Input:  {-3, 1, -3, 4, -1, 2, 1, -5, 4}
Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.

 


 

The idea is to find the sequence which will have maximum negative value. If we remove that minimum sum sequence from the input sequence, then we will be left with maximum sum circular sequence. Finally, we return maximum of the maximum-sum circular sequence (includes corner elements) and maximum-sum non-circular sequence.

 

For example, consider the array {2, 1, -5, 4, -3, 1, -3, 4, -1}. The sequence having maximum negative value is {-5, 4, -3, 1, -3} i.e. -6. If we remove this minimum sum sequence from the array, we will get the maximum sum circular sequence i.e. {2, 1, 4, -1} having sum 6. Since maximum sum circular sequence is greater than the maximum sum non-circular sequence i.e. {4} for the given array, it is the answer.

 

We can find maximum-sum non-circular sequence in linear time by using Kadane’s algorithm. We can find maximum-sum circular sequence by inverting the sign of all array elements and then applying Kadane’s algorithm.

For example, if we invert signs of array {2, 1, -5, 4, -3, 1, -3, 4, -1} we get {-2, -1, 5, -4, 3, -1, 3, -4, 1} which has maximum sum sequence {5, -4, 3, -1, 3} having sum 6. Now inverting the signs back, we get minimum sum sequence {-5, 4, -3, 1, -3} having sum -6.

 
C++ implementation –
 

Download   Run Code

Output:

The sum of subarray with the largest sum is 6

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂