(Hacker Rank) The Maximum Subarray - Solution

Link to the problem: https://www.hackerrank.com/challenges/maxsubarray

In order to obtain the maximum possible sum of a non-contiguous sub-array, we only consider the positive elements. If there is not any positive element, we consider the maximum negative element.

On the other hand, to obtain the maximum possible sum of a contiguous subarray, we keep an array of sums. In this array, we keep the sum of all the elements until the current position (inclusive). If the sum is negative, we replace it by zero in the array. Then, the answer is the biggest value that we have in this array. PS.: It can also be done without using the array.


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numElements = sc.nextInt();
            int[] elements = new int[numElements];
            for (int j = 0; j < numElements; j++) {
                elements[j] = sc.nextInt();
            }
           
            int maxNegativeElement = -100000;
            int maxSumNonContiguous = 0;
            int countPositive = 0;
            for (int j = 0; j < numElements; j++) {
                if (elements[j] >= 0) {
                    maxSumNonContiguous += elements[j];
                    countPositive++;
                }
                else {
                    maxNegativeElement = Math.max(maxNegativeElement, elements[j]);
                }
            }
               
            int[] sum = new int[numElements+1];
            int indexSum = 0;
            sum[indexSum++] = 0;
            int maxSumContiguous = -1000000;
            for (int j = 0; j < numElements; j++) {
                if (sum[indexSum-1]+elements[j] < 0) {
                    sum[indexSum] = 0;
                    indexSum++;
                    continue;
                }
                sum[indexSum]  = sum[indexSum-1]+elements[j];
                maxSumContiguous = Math.max(maxSumContiguous, sum[indexSum]);
                indexSum++;
            }
            if (maxSumContiguous == -1000000) {
                maxSumContiguous = maxNegativeElement;
            }
           
            System.out.print(maxSumContiguous + " ");
            if (countPositive > 0) {
                System.out.println(maxSumNonContiguous);
            }
            else {
                System.out.println(maxNegativeElement);
            }
        }
    }
}