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++

Download   Run Code

Output:

The sum of subarray with the largest sum is 6

Java

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).

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
asdf
Guest

nice

Allen
Guest

Should negMaxSum = -kadane(A) instead of kadane(A)? As this number should be negative.

Josh
Guest

I think it is already implied in this expression: Arrays.stream(arr).sum() + negaMaxSum which is equivalent to Arrays.stream(arr).sum() – (-negaMaxSum)