Problem Statement:

In Byteland there is a circular colony of N houses . Each house in the colony has some money. The value of money can either be positive or negative. Find the maximum amount of money you can have after robbing any number of contiguous houses.
Note: Robbing a house having negative money will reduce your money by that amount.
Input:
First line of input contains a single integer T which denotes the number of test cases. First line of each test case contains a single integer N which denotes the total number of houses. Second line of each test case contains N space separated integers denoting money in the houses.
Output:
For each test case print the maximum money by robbing the consecutive houses.
User Task:
The task is to complete the function maxMoney() which returns the maximum money.
Constraints:
1 <= T <= 100
1 <= N <= 106
-106 <= Arr[i] <= 106
Example:
Input:
3
7
8 -8 9 -9 10 -11 12
8
10 -3 -4 7 6 5 -4 -1
8
-1 40 -14 7 6 5 -4 -1
Output:
22
23
52
Explanation:
Testcase 1: Starting from last house of the colony, robbed 12 units and moving in circular fashion, we can rob 8, -8, 9, -9, 10, which gives maximum robbed monney as 22.

My Approach:

// { Driver Code Starts

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


 // } Driver Code Ends
//User function Template for C++

// arr: input array
// num: size of array
#include<math.h>

int kadane(int a[],int size,int start)
{
    int curr_max = a[start];
    int max_so_far = a[start];
    int i = (start + 1 ) % size;
    while( i != start)
    {
        curr_max = max(a[i],curr_max+a[i]);
        max_so_far = max(max_so_far,curr_max);
        i = (i+1) % size;
    }
    return max_so_far;
}

int  maxMoney(int a[], int num)
{
   int val = 0;
   int i = 0;
   for(i = 0;i<num;i++)
   {
        int temp = kadane(a,num,i);
        if(val < temp)
            val = temp;
   }
    
   return val;
}

// { Driver Code Starts.

int main()
 {
	int T;
	cin>> T;
	
	while (T--)
	{
	    int num;
	    cin>>num;
	    int arr[num];
	    for(int i = 0; i<num; i++)
	        cin>>arr[i];
	    
	    
	    cout << maxMoney(arr, num) << endl;
	    
	}
	
	return 0;
}  // } Driver Code Ends