Max Circular Subarray Sum

Max Circular Subarray Sum

Max Circular Subarray Sum

Given an array arr[] of N integers arranged in a circular fashion. Your task is to find the maximum contigious subarray sum.

For each test case print the maximum sum obtained by adding the consecutive elements.

For Input:
2
15
787 656 543 291 27 165 659 736 232 351 237 28 75 207 274
22
658 195 -171 37 35 593 618 228 -57 -189 728 329 576 204 243 563 413 338 406 640 704 618

Your Output is:
5268
7955

Case 1:
If the max sum possible is including wrapping of elements that means circular behavior of the array results in a greater max sum then we will do:

~Invert the array
~find array sum
~using kadane, find max sum
~exclude the max sum from array total of array sum
~invert the final sum

This will give us the max sum using wrapping

Case2:
Simple kadane algo, without element wrapping

#include<bits/stdc++.h>
using namespace std;

int nowrap(int n, int arr[]){
    int sum_so_far =INT_MIN, max_sum=0;
// in given array finding max by kannadiean algo
    for(int i=0; i<n; i++){
        max_sum += arr[i];
      
        if(sum_so_far<max_sum){
            sum_so_far = max_sum;
        }
         if(max_sum<0){
            max_sum = 0;
        }
    }
    return sum_so_far;
}

int wrap(int n, int arr[]){
// multiply the array element with -1 to reverse
    for(int i=0;i<n;i++){
        arr[i] = -1*arr[i];
    }
    int sum_so_far = 0, max_sum = 0, sum = 0;
//finding maximum sum by kannadian algorithm
    for(int i=0; i<n; i++){
        max_sum += arr[i];
        //if current sum greater than sum so far then assign current sum to sum so far
        if(sum_so_far<max_sum){
            sum_so_far = max_sum;
        }
//if current sum that is max_sum is less than 0 then assign zero
        if(max_sum<0){
            max_sum = 0;
        }
        sum += arr[i];
    }
//actually max_so_far is minimum value and total sum is sum
// by substracting total sum - minimum value to get maximum sum
    return (sum_so_far-sum);
}

int main()
 {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin>>t;
    while(t--){
        int n; cin>>n;
        int arr[n];
        for(int i=0; i<n; i++){
            cin>>arr[i];
        }
//finding maximum sum from array
        int a = nowrap(n, arr);
//finding maximum sum from array by revering array
        int b = wrap(n, arr);
         if(b==0)
         cout<<a<<endl;
         else
         cout<<max(a, b)<<endl;
    }
    return 0;
}