Maximum circular sum

#1

#include
#include
using namespace std;
int kad(int a[],int n);
int maxcir(int a[],int n);
int maxcir(int a[],int n){
int mkad=kad(a,n);
int i,w=0;
for(i=0;i<n;i++){
w+=a[i];
a[i]=-a[i];

}
w=w+kad(a,n);
return(w>mkad)?w:mkad;

}
int kad(int a[],int n){
int cs=0,ms=0;
for(int i=0;i<n;i++){
cs+=a[i];
if(cs<0){
cs=0;
}
if(ms<cs){
ms=cs;
}
}
return ms;
}
int main() {
int t,n;
cin>>t;
while(t–){
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>n;
}

	cout<<maxcir(a,n)<<endl;
	
}

return 0;

}sir why this code is not working?

#2

@gouravemmanuel Please save your code on ide.codingblocks.com and share its link. It is easy for us to debug then.
Until then check if you are correct with your logic. I am giving the approach:

For maximum circular sub array sum you need to consider the maximum of these 2 cases:

  1. The maxm sum subarray is obtained in non circular fashion as in normal Kadane’s algorithm.Apply normal Kadane on the array and obtain this.
  2. The maxm circular sub array sum is obtained in a circular fashion.

To compute the 2nd case:
As you know that Kadane algo gives the maxm subarry sum…so if you invert the sign of each element of the array and then apply Kadane, the maxm subarray sum now obtained will actually be the minimum subarray sum for the original array.
Consider array elements as: 1 2 -1 -3 4 6
1.maximum subarray sum in non circular fashion is: 4+6=11
2. on inverting the signs, the array becomes: -1 -2 1 3 -4 -6
Now applying Kadane, maxm subarry sum is: 1+3=4
So minimum subarray sum for the original array is: -4
3. Now cumulative sum of the original array is: 1+2-1-3+4+6= 9
If you subtract the minimum sub array sum from cumulative sum you get: 9-(-4)=13 which is actually the
maximum subarray sum in circular fashion ie. 4+6+1+2=13 .
So now the answer will be max(11,13)=13.

#3
#4

sir i hv shared the link plz check

#5

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.