not able to understand the editorial,pls explain why we have added instead of subtracting the maximum sum subarray after inverting
Maximum circular subarray
To calculate maximum circular subarray, there will be two cases :
Case 1 : Elements are arranged such that there is no wrapping , 10, -3, -4, 7, 6, 5, -4, -1
here the cumulative value will be : 10-3-4+7+6+5-4-1=16 , this is produced as per Kadane’s algo
case 2: The elements which contribute to maximum sum are arranged such that there is wrapping, Thus we will invert sign of all elements and then calculate sum based on Kadane’s algo:
for eg : -10, 3, 4, -7,-6,-5,4,1
it will produce result as : - 7
thus maximum sum will be : array - sum - (-max subarray sum of inverted array)
thus we will get array sum +max subarray sum of inverted subarray
thus the ans to above eg will be 16+7 = 23
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.