Maximum Circular Subarray Sum (Editorial)

#1

So if we subtract the negative value of this
new sum from the cumulative sum of the original array we will get another candidate for the
answer and name it candidate2.

MY DOUBT IS WHY
array-sum - (-max subarray sum of inverted array) WHY NOT
array-sum - (max subarray sum of inverted array)
Because its the minimum of original array.

Maximum circular sum
Maximum circular Subarray sum editorial of CB odf is given
Maximum Circular Sum
I dont understand editorial
#2

@sounakume
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.

Maximum Circular Sum
#4

I understood the algorithm completely but my question was when we are generalising as formula we are not doing
max_wrap = max_wrap - kadane of inverted array(which is the minimum of original array)

we are doing
max_wrap = max_wrap + kadane of inverted array(which is the minimum of original array).

shouldn’t we do first one because eventually what the results comes from kadane of inverted array(which is the minimum of original array) should decide the sign between them.

#5

When you invert an array an then apply kadanes algorithm…say you get the maximum subarray sum for the inverted array as x. Since the array was inverted, this will be -x for the original array.
So max_wrap = max_wrap - (-x)
=max_wrap +x

Hope you get that.

Circular sum subarray under array
#6

Ok I got it. Thanks You.

#7

i didn’t understand the subtract part because in the code we are not doing any subtraction

Maximum circular sum
#8

i didn’t understand the subtract part because in the code we are not doing any subtraction

#9

@Somith When you invert an array an then apply kadanes algorithm…say you get the maximum subarray sum for the inverted array as x. Since the array was inverted, this will be -x for the original array.
So max_wrap = max_wrap - (-x)
=max_wrap +x

So this eventually becomes addition… Take an example case and check it by yourself. You will understand.

#10

how do you get this logic in first go ? i am not able to think, what should i do ?

#11

in editorial , in case 2 they are finding max_wrap first and then they are doing arr[i] = -arr[i];
But in you explanation you are changing signs first and then calculating sum.

i dont understand can you please explain in detail ?

#12

All my test cases are passing except the first test case. Please help.