how to traverse array circularly
Circular sum subarray
#include using namespace std; int main() { int t; cin>>t; while(t>0) { int n; cin>>n; int arr[n]; for(int i=0;i<n;i++) { cin>>arr[i]; } int b[2n]; for (int i = 0; i < n; i++) { b[i] =arr[i]; } for(int i=0;i<n;i++) { b[n+i]=arr[i]; } int cs=0,ms=0; for(int i=0;i<2n;i++) { cs=cs+b[i]; if(cs<0) { cs=0; } else if(cs>ms) { ms=cs; } } cout<<ms<<endl; t–; } return 0; }
For this algo, you will use two approaches, firstly you will calculate component 1 using the kadane’s algo and then invert the given array and then calculate the component 2 again using kadane’s algo, and then compare the two components and return max of them.