please see if my logic is correct
first i found the max element from the array then keeping the first iteration from the address of max element i iterated n times in a circular manner .
Test cases not passing
hello @ashishxmathew
no thats not completely correct.
from each index i , find maximum sum that u can get by considering next n elements(including i ). (ie assume each index as starting point of array and find maximum using kadane , repeat this for all indices and get maxmimum)
and pick maximum of among all value…
optimised one->
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
check this.
i dont your answer seems absolutely correct but none of the test case are passing i tried it with the custom input it was correct. even for my code none of the test cases were passing i thought atleast one should pass.??
which code u r submitting pls share the link with me.
if it is brute force one then it will give tle
i got it . forgot to add endl so all the output were printed without spaces. hence the error