 Recent Tutorials and Articles
HackerRank Solution: The Maximum Subarray
Published on: 25th May 2018

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

# Hackerrank Challenge Details

### Problem Statement:

Given an array A = {a1, a2, a3, ..., aN} 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 < 105
• -104 < ai < 104

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.

Published on: 25th May 2018