Maximum circular sum

#1

can you provide some hint for this question?

#2

Hey @shubhangis248

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

Maximum circular subarray
#3


what is wrong in this code?

#4

Hey @shubhangis248

   for(int i=0;i<n;i++)
   {
       for(int j=i;j<n;j++)//Here it should be j=i
       {
		   sum=0;//added this
           for(int k=i;k<=j;k++)
           {
               sum+=a[k];
           }
           if(minsum>sum)
           minsum=sum;
       }
   }

This will still give u TLE for some cases because u are calculating minsum in O(n^2)
Calculate it just like maxsum in O(n)

#5

now,what is wrong in this code?

#6

@shubhangis248

   {
       sum+=a[i];
       if(sum>0)sum=0;//added this

       minsum=min(sum,minsum);
   }

If this resolves ur query then please mark it as resolved :slight_smile: