The Kadane’s algorithm minimum sum variant passes all the testcases for Max Circular Subarray Sum problem on Leetcode, but fails to pass any testcase here (gives Wrong Answer). Am I doing anything wrong? (providing my code below)
include iostream
include climits
using namespace std;
int main() {
int t;
cin>>t;
for(int j=0; j<t; j++){
int n;
cin>>n;
int a[n];
int ttl_sum=0,all_neg = 1, max_val = INT_MIN;
for(int i=0; i<n; i++){
cin>>a[i];
ttl_sum+=a[i];
if(a[i]>0) all_neg=0;
max_val = max(max_val,a[i]);
}
if(all_neg==1){
cout<<max_val;
continue;
}
int max_sum = 0, sum = 0;
for(int i=0; i<n; i++){
sum+=a[i];
max_sum = max(max_sum,sum);
if(sum<0) sum=0;
}
int min_sum=0;
sum=0;
for(int i=0; i<n; i++){
sum+=a[i];
min_sum = min(min_sum,sum);
if(sum>0) sum=0;
}
int out = max(max_sum, ttl_sum-min_sum);
cout<<out;
}
return 0;
}
…