I am not able to figure out logic for this problem

#1

please give logic for this problem, i will then try to implement myself.

#2

hello @agarwalarjit.agarwal
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.

image
image890×300 25.4 KB

  • 1+2+5 = 8
  • For non circular sum,
    Step 1) find the minimum subarray sum of array.

image
image851×281 23.7 KB

-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

#3

how did we find sum of circular array, what is the logic behind it?

#4

here it is mentioned

#5

getting wong answer for all the testcases

#6
#7

logic for getting min subarray is not correct.

logic to get min subarray.
a) chnage the sign of all the array elements
b) then apply kadane on that array
c) let say x is the max sum u get . then -x will be the required min sum subarray.

also use long long in place of int

#8

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.