#include
using namespace std;
int max_circular_sum(int a[],int n)
{
int i,j,cs,ms=0;
for(i=n-1;i>=1;i–)
{
if(a[i]>0)
cs=a[i];
else
cs=0;
for(j=0;j<i;j++)
{
cs+=a[j];
if(cs<0)
cs=0;
if(cs>ms)
ms=cs;
}
}
return ms;
}
int main() {
int t;
cin>>t;
for(int j=0;j<t;j++)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<max_circular_sum(a,n)<<endl;
}
return 0;
}
Hi @tushartiwari,
in dis,
for(i=n-1;i>=1;i–)
{
if(a[i]>0)
cs=a[i];
else
cs=0;
for(j=0;j<i;j++)
{
cs+=a[j];
if(cs<0)
cs=0;
if(cs>ms)
ms=cs;
}
}
when i=n-2, ur code only calculate sum upto n-2 and n-1 is not considered.
this is true for all i<n-1. hence ur code is not accounting for circular sum.
try modifying ur code.
if u face any problem, feel free to post ur doubt here.
can you give some hint .
@tushartiwari,
u can use kedane algo to solve this problem.
1)find maximum sum subarray using kedanes algorithm.
2)convert all elements of array a[i] to -a[i]. now again apply kedanes algo to get max sum. in this case , the max sum u will get(by converting array to -a[i]) will be minimum sum wrt to original array. now add this sum to sum of all elemnts of original array(since the sum u computed is -ive wrt to original array).
3)print max of (1) and (2)
eg. 5 -1 -2 3 4.
using kedane u will get max sum as (5-1-2+3+4)=9.
now convert whole array to -a[i].
array=-5 1 2 -3 -4
calculate max sum=(1+2)=3.
subtact this sum from original array total sum i.e 9+3=12.
hence max sum possible =12
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.