Circular sub array max sum

#1

please explain the minimum sum of array concept and subtraction of its negative value to the array sum giving the max circular sum

#2

For maximum circular sub array sum you need to consider the maximum of these 2 cases:

  1. The maxm sum subarray is obtained in non circular fashion as in normal Kadane’s algorithm.Apply normal Kadane on the array and obtain this.
  2. The maxm circular sub array sum is obtained in a circular fashion.

To compute the 2nd case:
As you know that Kadane algo gives the maxm subarry sum…so if you invert the sign of each element of the array and then apply Kadane, the maxm subarray sum now obtained will actually be the minimum subarray sum for the original array.
Consider array elements as: 1 2 -1 -3 4 6
1.maximum subarray sum in non circular fashion is: 4+6=11
2. on inverting the signs, the array becomes: -1 -2 1 3 -4 -6
Now applying Kadane, maxm subarry sum is: 1+3=4
So minimum subarray sum for the original array is: -4
3. Now cumulative sum of the original array is: 1+2-1-3+4+6= 9
If you subtract the minimum sub array sum from cumulative sum you get: 9-(-4)=13 which is actually the
maximum subarray sum in circular fashion ie. 4+6+1+2=13 .
So now the answer will be max(11,13)=13.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

Thanks,the doubt is solved .But I say that there should be (minimum sub array sum)=-(max sub array sum for inverted array) which though clarified in the illustration above might make it better to understand if written instead of (minimum sub array sum) is the (max sub array sum for inverted array).