I cannot understand the question from the description… kindly help me with the approach …
I tried to do the question by kadane algo and to make the array circular the sum of last and first element is calculated … …
Maximum sum in circular subarray
hello @aavruty_dhir
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
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.
what is the logic behind max subarray circular sum being either maximum subarray sum in non circular array or maximum subarray sum in circular array.
…
see the array is circluar .
a) if array is not circular, then this problem is simple kadane problem.
so for that we can run our standard kadane.
b) now becuase array is circluar , the corner elements of array can also form maximum.
something like this->
in above approach we are talking about these two cases only.
there is no other case possible. to get maximum
what is the algorithm for finding the minimum sum subarray
…
i already rpelied in ur chat.
what is the issue in this
check now->