Given an array of elements, find the maximum possible sum of a

- Contiguous subarray
- 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 . cases follow.

Each test case begins with an integer . In the next line, integers follow representing the elements of array .

**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**

**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 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; }