not able to get the logic
Not able to get the logic
hello @dipeshpandey2001
The maximum subarray sum in circular array is maximum of following
- Maximum subarray sum in non circular array
- Maximum subarray sum in circular array.
Example - [1,2,5,-2,-3,5]
Steps -
- Find the maximum subarray sum using Kadane Algorithm. This is maximum sum for non circular array.
- 1+2+5 = 8
- For non circular sum,
Step 1) find the minimum subarray sum of array.
-2-3 = -5
Step 2) Now find the total sum of array = 1 + 2 + 5 -2 - 3 + 5 = 8
Step 3) The max subarray sum for circular array = Total Sum - Minimum subarray Sum
= 8 - (-5) = 8 + 5 = 13
As illustrated above, substracting minimum subarray sum from total sum gives maximum circular subarray sum.
Answer = Max ( Non circular max sum + circular max sum ) = max(8,13) = 13
c2+=a[i]; a[i]=-a[i]; not understood these two lines
line number 25 and 26
adding c2 holds sum so in line 26 we are adding arr[i] to c2 .
and in line 27 we are chanign the sign of a[i] ,read above response again , it will make sense
still not understood,why do we need to change the sign?
…
to find the minimum sum of subarray we need to flip array size and then apply kadane over it.
can you pls send the explanation once again,which you send earlier,its not showing now.
use this link ->
okay;thanks)…
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.