Answer getting wrong for maximum circular sum

#1

#include
using namespace std;
int kadne(int b[],int n){
int k=0;
int cf=0;
for(int i=0;i<n;i++){
if(cf<0){
cf=0;
}
k=k+b[i];
if(k>cf){
cf=k;
}
}
return cf;
}
int main() {
int i,t,j,n;
cin>>t;
while(t–){
int a[100],max=0;
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
int b[100];
for(j=0;j<n;j++){
b[j]=a[(i+j)%n];
}
int o= kadne(b,n);
if(max<o){
max=o;
}
}
cout<<max;
}
return 0;
}

#2

Hi!
In this problem, there will be 2 cases:
When max sum is given without wrapping:
Example: 1,-2,10,11,-1,20,-50
here 10,11,-1,20 will give the max sum, simple case : here kadane’s algo will work fine

case 2: Wrapping:
Example: -1 100 -10 17 3 4 -2 -2
here max sum will be given by 17,3,4,-2,-2,-1,100
wrapping is there, as we are starting at 17 then going on till -2,-2 and then going at -1,100 (as its a circular array so we can start from any point), here simple Kadane’s algo won’t work.

consider both the cases.

#3
#4

check the link solved with same algo as described

#5

let me see the problem

#6

The approach is not same as descibed earlier,
You’re correct in the part that you have to apply kadan’e algorithm, but you also have to make another function to take care of the second condition. The point is to make sure that the maximum answer gets printed.
The function should look like this:

circularSum(a[], n){
// kadane(a,n): maximum sum using kadane’s algo
sum_without_wrapping = kadane(a, n);
// Case 2: wrapping
sum_wrapping = 0,i;
for (i=0; i<n; i++){
//array sum
sum_wrapping += a[i];
a[i] = -a[i];
}
sum_wrapping = sum_wrapping + kadane(a, n);
if(sum_wrapping>sum_without_wrapping){
// cout<<“wrapping”<<endl;
return sum_wrapping;
}
else{
// cout<<endl<<"…"<<endl<<“no wrap”<<endl;
return sum_without_wrapping;
}
}

#7

I am not getting algo of adding sum_wrap.plz help me here

#8

See the basic approach here is:
In case 2, we are calculating the elements which do NOT contribute to sum:
Example: -1,100,-10,17,3,4,-2,-2
Lets dry run the code for ^ array
Now, after running the loop, sum_wrapping will be simply equal to the total sum, but the sign of elements would be inverted due to a[i] = -a[i]

Now, we will subtract the non contributing elements from total sum.
That is what we are doing in this step:

sum_wrapping = sum_wrapping + kadane(a, n)

Now, the question might arise that how does it help our cause,
So what happens is that when we invert the sign and run Kadane’s algo, it helps us to reduce the damage i.e. it helps us in identifying the maximum continuous negative.
See the above example:
after the sign is inverted, the array becomes

1, -100, 10, -17, -3, -4, 2, 2

applying Kadane’s algo on the above code will give 10
if you subtract 10 from total sum 119, then it turns out to be 109, which is the answer in this case given by 17,3,4,-2,-2,-1,100