Kadane's Algorithm

Question: Given an array arr of N integers. Find the contiguous sub-array with maximum sum.

Asked in various companies like Microsoft,Amazon and Walmart 
#include<algorithm>
using namespace std;

int maxSubArraySum(int arr[], int n) 
{ 
    int max_so_far = INT_MIN, max_ending_here = 0; 
    for (int i = 0; i <n; i++) 
    { 
        max_ending_here = max_ending_here + arr[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) 
            max_ending_here = 0; 
    } 
    return max_so_far; 
} 
int main() 
{ 
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        int arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
         int max_sum = maxSubArraySum(arr, n); 
          cout <<max_sum<<endl; 
    }
    return 0; 
}