#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int loop;
    cin >> loop;
    while (loop--) {
        int size;
        cin >> size;
        vector<int> data(size, 0);
        for (int i = 0; i < size; ++i) {
            cin >> data[i];
        }

        vector<int> dp(size, 0);
        int big = 0;
        int sum = 0;
        int start = -1;
        for (int i = 0; i < size; i++) {
            int val = sum + data[i];

            if (val > 0) {
                if (sum == 0) {
                    start = i;
                }
                sum = val;
            } else {
                sum = 0;
            }

            if (sum > big) {
                big = sum;
            }
        }

        if (start == -1) {
            cout << data[0] << " ";
        } else {
            cout << big << " ";
        }

        sum = 0;
        start = -1;
        for (int i = 0; i < size; ++i) {
            if (data[i] > 0) {
                start = i;
                sum += data[i];
            }
        }

        if (start == -1) {
            cout << data[0] << endl;
        } else {
            cout << sum << endl;
        }
    }
    return 0;
}

• Problem Description
  Given an array A={a1,a2,…,aN} of N elements, find the maximum possible sum of a Contiguous subarray Non-contiguous 
  (not necessarily contiguous) subarray.
  
  Empty subarrays/subsequences should not be considered.
  
  Input Format
  
  First line of the input has an integer T. T cases follow. 
  Each test case begins with an integer N. In the next line, N integers follow representing the elements of array A.
  
  Constraints
  1<=T<=10 
  1<=N<=10^5 
  -10^4<=ai<=10^4
  The subarray and subsequences you consider should have at least one element.
  
  Output Format
  
  Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).
  
• Test Case 1
  Input (stdin)2
  4
  1 2 3 4
  6
  2 -1 2 3 4 -5
  Expected Output10 10
  10 11
• Test Case 2
  Input (stdin)1
  6
  2 -1 2 3 4 -5
  Expected Output10 11