## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# The maximum continuous and non-continuous subarray challenge

Sharing is caring!

Problem statement
Given an array $A=\left[a_1, a_2, \dots, a_N\right]$ 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.

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 \le T \le 10$
$1 \le N \le 10^5$
$-10^4 \le a_i \le 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).

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:
$\left[2, -1, 2, 3, 4\right]$ –> 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 $1$) 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.

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:

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 $\mathcal{O}(n)$

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 $\left[2, -1, 2, 3, 4, -5\right]$ will become $\left[-5, -1, 2, 2, 3, 4\right]$ 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:

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 $\mathcal{O}(nlogn)$

The full code for both version is listed below.

Full code

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

}
}
}