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

Hackerrank Challenge Details

Problem Statement:

Given an array A = {a₁, a₂, a₃, ..., 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.

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⁵
• -10⁴ < a_i < 10⁴

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.