What should be the concept behind this problem

#1

help me out in getting the concept of this

#2

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.

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

1 Like
#3

it’s really appreciable.thanks a lot

#4

if this solves your doubt please mark it as resolved :slight_smile:

1 Like
#5

how to mark it as resolved

#6

there is a problem in marking doubts now, it’ll be resolved soon. i ll mark it resolved on your behalf for now :slight_smile:

1 Like