how to approach with this problem
My circular sum sub array is failing test cases
The maximum subarray sum in circular array is maximum of following
- Maximum subarray sum in non circular array
- Maximum subarray sum in circular array.
Example - [1,2,5,-2,-3,5]
Steps -
- Find the maximum subarray sum using Kadane Algorithm. This is maximum sum for non circular array.
- 1+2+5 = 8
- For non circular sum,
Step 1) find the minimum subarray sum of array.
-2-3 = -5
Step 2) Now find the total sum of array = 1 + 2 + 5 -2 - 3 + 5 = 8
Step 3) The max subarray sum for circular array = Total Sum - Minimum subarray Sum
= 8 - (-5) = 8 + 5 = 13
As illustrated above, substracting minimum subarray sum from total sum gives maximum circular subarray sum.
Answer = Max ( Non circular max sum + circular max sum ) = max(8,13) = 13
But my code was working sample input
pls check it once whether i could make any change in this
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
int n;
while(t–){
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int b[n];
b[0] = a[n-1];
int k=0;
for(int i=1;i<n;i++){
b[i] = a[k++];
}
int max_so=b[0];
int maxy=b[0];
for(int i=1;i<n;i++){
max_so = max(b[i] , max_so+b[i]);
if(max_so > maxy ){
maxy = max_so;
}
}
cout<<maxy<<endl;
}
}
whats ur logic of the code ?
share code on cb ide
why are u rotating
it wont help
please understand the explanation i have provided that is the easiest way to go about this question
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.