The Maximum Subarray.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int max(int a, int b) {
    return a >= b ? a : b;
}

void solve() {
    int n, i, x, best_sum=INT_MIN, current_sum=INT_MIN;
    int max_here=INT_MIN, max_sofar=INT_MIN;
    
    cin >> n;
    cin >> x;
    
    max_here = max_sofar = x;
    current_sum = best_sum = x;
    
    for(i=1; i<n; i++){
       cin >> x;    
       
       max_here = max(max_here, max_here + x);
       max_sofar = max(max_here, max_sofar);
    
       current_sum += x;
       if (current_sum >= best_sum) {
           best_sum = current_sum;
       } else {
           if (current_sum < 0)
               if (x >=0)
                   current_sum = x;
               else
                   current_sum = 0;
       }
    }
    
    cout<<best_sum<<" "<<max_sofar<<"\n";
}

int main() {
    int t, i;
    cin>>t;
    
    for(i=0; i<t; i++) {
        solve();
    }
    return 0;
}