Circular subarray

#1

#include
using namespace std;

int maxmsub( int a[],int n)
{ int maxtotal=a[0];
int mintillhere=a[0];
int maxtillhere=a[0];
int mintotal=a[0];
int s=0;

for(int i=0;i<n;i++)
{  
  if(maxtillhere+a[i]>a[i])
  {
  	 maxtillhere+=a[i];
  }
  else
  {
   maxtillhere=a[i];
  }
  maxtotal=max(maxtotal,maxtillhere);
  
  if(mintillhere+a[i]<a[i])
  { 
    mintillhere+=a[i];
  }
  else
  {
  	mintillhere=a[i];
  }
  mintotal=min(mintotal,mintillhere);
  
  s+=a[i];	    
}
	  if(s==mintotal)
  {
  	return maxtotal;
		}
  
  return max(s-mintotal,maxtotal);

}

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a[100000]={0};
for(int i=0;i<n;i++)
{
cin>>a[i];

	}
   cout<< maxmsub(a,n);
	
}

}

is the logic incorrect??

#2

anybody reply?? please

#3

you need to take circular sum in the consideration.
how to do it?
step1. run kadane’s algo in the array, store ans in x.
step2. for every index i, sum up the max prefix sum to i and max suffix sum from i+1.
get the max of all, and store it in y.
for eg. the array is 4 5 -3 2 -8 9 -7 9… then say i = 3,
max prefix sum is 9(5 +4), max suffix sum is 11(9-7+9). their sum is 20. you can see that this is one possible circular sum. you need to do it for every index i and compute max among all these values and store this in y.

step3. return max(x,y)

thanks

#4

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.