Maximum circular subarray sum

#1

i dont get any point in this question ;
what is circular subarray;
what are they doing in solution by inverting signs and calculating cumulative sums
???

How to iterate circularly
Maximum circular sum
Algo for this prob
Circular subarray sum
#2

@soorya19k Consider a simple array. Imagine that the last element of this array becomes adjacent to the first element. This this would be called a circular array. Subarrays of this array will be circular subarray.

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

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