We define subsequence as any subset of an array. We define a subarray as a contiguous subsequence in an array.
Given an array, find the maximum possible sum among:
- all nonempty subarrays.
- all nonempty subsequences.
Print the two values as space-separated integers on one line.
Note that empty subarrays/subsequences should not be considered.
Example
The maximum subarray sum is comprised of elements at inidices . Their sum is . The maximum subsequence sum is comprised of elements at indices and their sum is .
Function Description
Complete the maxSubarray function in the editor below.
maxSubarray has the following parameter(s):
- int arr[n]: an array of integers
Returns
- int[2]: the maximum subarray and subsequence sums
Input Format
The first line of input contains a single integer , the number of test cases.
The first line of each test case contains a single integer .
The second line contains space-separated integers where .
Constraints
The subarray and subsequences you consider should have at least one element.
Sample Input
2
4
1 2 3 4
6
2 -1 2 3 4 -5
Sample Output
10 10
10 11
Explanation
In the first case:
The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).
In the second case:
[2 -1 2 3 4] --> This forms the contiguous sub-array with the maximum sum.
For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.