# The Maximum Subarray

Given an array $A=\{a_1,a_2,\dots,a_N\}$ of $N$ elements, find the maximum possible sum of a

1. Contiguous subarray
2. Non-contiguous (not necessarily contiguous) subarray.

Empty subarrays / subsequences should not be considered.

Problem Source : Hackerrank

Input

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$.

Output

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).

Constraints

• $1 \leq T \leq 10$
• $1 \leq N \leq 10^5$
• $-10^4 \leq a_i \leq 10^4$

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.

Solution

It would be relatively easier if the problem allows an empty subarray. Then, we could simply apply Kadane’s Algorithm, an algorithm to find the maximum subarray with $O(n)$ runtime efficiency.

Pseudocode

tmax = smax = 0
for x in A:
tmax = max(0 , tmax + x)
smax = max(tmax , smax)
print smax


Properties of a maximum subarray

• It’s either empty or consists of elements with positive summation.
• It only starts and ends with a positive number.
• The absolute value of the negative number in the maximum subarray is smaller than the sum of elements at its left.

With these properties in hand, the motivation behind Kadane’s Algorithm is clear. tmax looks for all positive contiguous sum of the array till the point x. When tmax is negative, it violates the third property of a maximum subarray. Hence, it starts the sum from 0 again and continue searching for positive contiguous segments. Everytime tmax has a new value, it is compared with smax to check if it’s the largest sum so far.

The problem, however, is that empty array is not allowed. Kadane’s Algorithm returns 0 when all the elements are negatives instead of the largest negative numbers. Fortunately, a slight variation of Kadane’s Algorithm can solve the problem.

tmax = smax = A[0]
for i = 1 to N-1:
tmax = max(A[i] , tmax + A[i])
smax = max(smax , tmax)
print smax


In this variation, tmax compares the current element with the contiguous sum. If the contiguous sum is smaller than the current element, it means that the previous contiguous sum is negative, so we only have to pick the current element at the moment. After we iterate through the array, if all of its elements are negatives, smax will return the largest negative element.

The other problem is to find the maximum sum of a non-contiguous subarray. We only have to take the sum of all positive integers in the array. If all of its elements are negatives, return the largest negative element ( Hint : smax ). In the following code, the maximum sum of a non-contiguous subarray is denoted as pmax.

C++

#include <iostream>

using namespace std;

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

int A[100001];

int main(){

int T;
cin >> T;

int N, smax, tmax, pmax;
for (int i=0; i<T; i++){
cin >> N;

cin >> A[0];
smax = tmax = A[0]; pmax = max(0, A[0]);
for (int j=1; j<N; j++){
cin >> A[j];

tmax = max(A[j], tmax + A[j]);
smax = max(smax, tmax);
pmax += max(0, A[j]);
}

cout << smax << " " << (smax < 0 ? smax : pmax);
cout << endl;
}

return 0;
}