**Problem statement**

Given an array of 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.

Input Format

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 .

**Constraints**

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

**Sample Input**

1 2 3 4 5 |
2 4 1 2 3 4 6 2 -1 2 3 4 -5 |

**Sample Output**

1 2 |
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:

–> 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 for contiguous subarray**

We first need to initialise our current `sum`

and `max`

variable with some value. For that we can use `sum = max = a[0]`

.

Next, we are going to iterate over our array (starting from index ) and have a look at the current elements. If the current element `a[i]`

is greater than `sum + a[i]`

, then we might as well try a new sum starting from element `a[i]`

and discard the current `sum`

. This is because adding `sum`

to `a[i]`

only decreases `a[i]`

, we *might* be better off starting a new sum with just `a[i]`

.

If the current element `a[i]`

is not greater than `sum + a[i]`

, that is `a[i]`

becomes greater by adding the current `sum`

, then it doesn’t make sense to try starting a new sum from just `a[i]`

and we *might* be better off carrying the current `sum`

with us.

1 2 3 4 5 6 7 8 |
for (int i = 1; i < a.length; i++) { if (a[i] > sum + a[i]) { sum = a[i]; } else { sum += a[i]; } . . . } |

Above I have used the term *might*. This is due to the fact that we need to check if we have a new maximum sum every time we update `sum`

.

The full code for the continuous part is listed below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
private static int solveContinuous(int[] a) { int sum = a[0]; int max = a[0]; for (int i = 1; i < a.length; i++) { if (a[i] > sum + a[i]) { sum = a[i]; } else { sum += a[i]; } max = Math.max(sum, max); } return max; } |

The running time of this algorithm is

**Solution for non-contiguous subarray**

For the non-contiguous subarray version of this problem we are going to sort our array first in ascending order. Then we can iterate over our array from right to left and keep adding elements to our current sum, `sum`

, until we have iterated over all elements or reached a point where adding an element to `sum`

only decreases it.

For example the input will become after sorting. Then starting with `sum = 4`

we continue updating `sum`

. Next, `sum`

becomes `sum = 4 + 3 = 7`

. Then it becomes `sum = 7 + 2 = 9`

. Continuing, `sum`

becomes `sum = 9 + 2 = 11`

. We then reach the element `a[1] = -1`

which would decrease `sum`

(`11 - 1 < 11`

), so we stop since all elements that would follow `-1`

, would be smaller than `-1`

and will also just decrease `sum`

.

The full code for the non-continuous part is listed below:

1 2 3 4 5 6 7 8 9 10 11 12 13 |
private static int solveNonContinuous(int[] a) { Arrays.sort(a); int i = a.length - 1; int sum = 0; do { sum += a[i]; i--; } while (i >= 0 && sum + a[i] >= sum); return sum; } |

The running time of this algorithm is

The full code for both version is listed below.

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
public class MaximumSubarray { private static int solveContinuous(int[] a) { int sum = a[0]; int max = a[0]; for (int i = 1; i < a.length; i++) { if (a[i] > sum + a[i]) { sum = a[i]; } else { sum += a[i]; } max = Math.max(sum, max); } return max; } private static int solveNonContinuous(int[] a) { Arrays.sort(a); int i = a.length - 1; int sum = 0; do { sum += a[i]; i--; } while (i >= 0 && sum + a[i] >= sum); return sum; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int tests = in.nextInt(); for (int t = 1; t <= tests; t++) { int n = in.nextInt(); int a[] = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } System.out.println(solveContinuous(a) + " " + solveNonContinuous(a)); } } } |