Recent Tutorials and Articles
    HackerRank Solution: The Maximum Subarray
    Published on: 26th July 2016

    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: 26th July 2016

    Comment Form is loading comments...