#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