This tutorial provides Java solution to "The Maximum Subarray" challenge of HackerRank.

# Hackerrank Challenge Details

**Problem Statement:**

Given an array A = {a_{1}, a_{2}, a_{3}, ..., a_{N}} of N elements, find the maximum possible sum of a

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

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

**Constraints:**

- 1
__<__T__<__10 - 1
__<__N__<__10^{5} - -10
^{4}__<__a_{i}__<__10^{4}

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

# Solution Details

**Java Implementation:**

```
package com.saintech.allprogtutorials.hackerrank.algos;
import java.util.Scanner;
/**
* @author Sain Technology Solutions
*
* Solution to Problem - https://www.hackerrank.com/challenges/maxsubarray
*
*/
public class TheMaximumSubarray {
public static void main(String[] args) {
final Scanner in = new Scanner(System.in);
// Get the no of test cases
final int T = in.nextInt();
for(int i = 0; i < T; i++) {
// Initialize max sum of not necessary contagious elements to MIN value of
// integer to cater to accommodate negative values as well
int maxSumElems = Integer.MIN_VALUE;
// Initialize max sum of contagious elements to MIN value of
// integer to cater to accommodate negative values as well
int maxSumOfContiElems = Integer.MIN_VALUE;
// Represents the sum of elements up to current index
int sumOfPrevContiElems = 0;
// Get the number of elements in Array
final int N = in.nextInt();
for(int j = 0; j < N; j++) {
final int elem = in.nextInt();
// If previous sum is negative, we reset it to zero as we need to calculate max sum
// of contagious elements. If we include negative sum, our total sum will be less. Hence
// will get rid of negative sum as we go.
if(sumOfPrevContiElems < 0) {
sumOfPrevContiElems = 0;
}
// Add current element to sum of previous contagious elements
sumOfPrevContiElems+= elem;
// Update the max sum of contiguous elements with previous contagious sum only if it is lesser
if(sumOfPrevContiElems > maxSumOfContiElems) {
maxSumOfContiElems = sumOfPrevContiElems;
}
// Work out the max sum of non-contagious (not-necessary contagious) elements as follows -
// 1. If we have positive numbers then it is simply sum of all positive numbers
// 2. Else it is the max negative number as adding two negative number always leads to less number.
// Hence, we first check if current element is positive -
// - If yes, we check if we have had positive numbers till current element by checking current max Sum
// - If current max sum is positive, we add current element to current max sum
// - Else, we discard the current max sum as it was negative and assign it to current element.
// - Else, we assign max sum to max of current sum and current element
if(elem > 0) {
if(maxSumElems < 0) {
maxSumElems = elem;
} else {
maxSumElems += elem;
}
} else {
if(maxSumElems < 0) {
maxSumElems = Math.max(elem, maxSumElems);
}
}
}
System.out.println(maxSumOfContiElems + " " + maxSumElems);
}
in.close();
}
}
```

Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.