Largest Sum Contiguous Subarray

kadaneAlgo.cpp

/*
Write an efficient C program to find the sum of contiguous subarray 
within a one-dimensional array of numbers which has the largest sum. 
*/
#include <iostream>
using namespace std;
int kadaneAlgo(int arr[],int n)
{
    if(n==1)
        return arr[0];
    
    int max_so_far=0;
    int max_ending_here=0;
    
    for(int i=0;i<n;i++)
    {
        max_ending_here+=arr[i];
        if(max_ending_here<0)
            max_ending_here = 0;
        if(max_ending_here>max_so_far)
            max_so_far = max_ending_here;
    }
    
    return max_so_far>0?max_so_far:-1;
}
int main() 
{
	//code
	int t;cin>>t;
	while(t--){
	    int n;cin>>n;
	    int arr[n];
	    for(int i=0;i<n;i++)
	        cin>>arr[i];
	    int ans = kadaneAlgo(arr,n);
	    cout<<ans<<'\n';
	}
	return 0;
}