Maximum circular sum

#1

can u make me understand this code . why we are inverting the array???

#2

@Ambuj-Singh-514796906079795 which code? Please provide me the mentioned code in Coding Blocks IDE.

#3

#include <bits/stdc++.h>

using namespace std;
int kadane(int a[],int n)
{
int currSum=0;
int maxSum=0;
for(int i=0;i<n;i++){
currSum = currSum + a[i];
if(currSum < 0){
currSum = 0;
}
maxSum = max(currSum,maxSum);
}
return maxSum;
}
int circularSum(int a[],int n){
int c1 = kadane(a,n);
int c2=0;
for(int i=0;i<n;i++){
c2 += a[i];
a[i]=-a[i];

}
c2 = c2 + kadane(a,n);
return (c2 > c1) ? c2:c1;

int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int a[1000];
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<circularSum(a,n)<<endl;
}
return 0;
}

#4

why is it necessary to give a[i]=-a[i]? PLease explain briefly with example…

#5

@Ambuj-Singh-514796906079795 hey it is for covering the case when the subarray is wrapped.
Suppose we have an array such that in middle their are negative numbers and corners have positive number. Now We have their sum, and then we invert the array(make it negative) then we apply kadane algorithm, Now the kadane algorithm will give use maximum sum, as I said we have more negative/big negative number in middle and now they will be positive and kadane will return their sum.
Now if we add the sum of Kadane and Sum calculated before we will get the sum of corner elements,
If this resolves your doubt mark it as resolve.d

#6

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.