Max Circular Sub-Array Sum

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

Input:
N = 7
arr[] = {8,-8,9,-9,10,-11,12}
Output:
22
Explanation:
Starting from the last element
of the array, i.e, 12, and 
moving in a circular fashion, we 
have max subarray as 12, 8, -8, 9, 
-9, 10, which gives maximum sum 
as 22.
#include<bits/stdc++.h>
using namespace std;


 // } Driver Code Ends
class Solution{
    public:
    // arr: input array
    // num: size of array
    //Function to find maximum circular subarray sum.
    int circularSubarraySum(int arr[], int num){
        
        
        
        
        int maxsum = -11111;
        int localsum = 0;
        for(int i = 0;i<num;i++)
        {
            localsum +=arr[i];
            if(localsum > maxsum)
            maxsum = localsum;
            if(localsum < 0)
            localsum = 0;
            
        }
        
        int totl = 0;
        for(int i = 0;i<num;i++){
            totl+=arr[i];
        arr[i] = - arr[i];
        }
        
        int maxsum2 = -11111;
        int localsum2 = 0;
        for(int i = 0;i<num;i++)
        {
            localsum2 +=arr[i];
            if(localsum2 > maxsum2)
            maxsum2 = localsum2;
            if(localsum2 < 0)
            localsum2 = 0;
            
        }
        
        
        maxsum2 = -maxsum2;
        
        totl = totl - maxsum2;
        if(totl == 0)
        return maxsum;
        else if(totl>maxsum)
        return totl;
        else 
        return maxsum;
        
        
        
        
    }
};

// { Driver Code Starts.

int main()
 {
	int T;
	
	//testcases
	cin>> T;
	
	while (T--)
	{
	    int num;
	    
	    //size of array
	    cin>>num;
	    int arr[num];
	    
	    //inserting elements
	    for(int i = 0; i<num; i++)
	        cin>>arr[i];
	        
	    Solution ob;
	    //calling function
	    cout << ob.circularSubarraySum(arr, num) << endl;
	    
	}
	
	return 0;
}  // } Driver Code Ends
  1. TCS NQT CODING QUESTION
  2. Practice Link

Leave a Comment

Your email address will not be published. Required fields are marked *