The Maximum Subarray

The Maximum Subarray

Given an array  of  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 .  cases follow.
Each test case begins with an integer . In the next line,  integers follow representing the elements of array .

Constraints:

• 1<=T<=10
• 1<=N<=100000
• -10000<=ai<=10000

The subarray and subsequences you consider should have at least one element.

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

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.

This is not at all easy, it needs to calculate maximum values for both consecutive and sparse maximum summaries, and you need to know that famous solution to max subarray. Also finally you need to pay attention to how sparse maximum summaries can be calculated.

package DP;

import java.util.Scanner;

/**
 * Created by AndrewLocal on 7/2/2016.
 */

public class MaxSubarray {
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in  =  new Scanner(System.in);
        int N = in.nextInt();in.nextLine();
        for(int i=0;i<N;i++){
            int n = in.nextInt();in.nextLine();
            int a[] = new int[n];
            for(int j=0;j<n;j++)
                a[j]=in.nextInt();
            if(in.hasNextLine())in.nextLine();
            process(a);
        }
        in.close();
    }
    private static void process(int[] a){
        int cSum = a[0];
        int sSum[] = new int[a.length];//sparse, adding numbers only when it makes total bigger
        int cSumMax = a[0];
        //cSum[0]=a[0];
        sSum[0]=a[0];
        for(int i=1;i<a.length;i++){

//-1 2: -1+2>-1 but I'd rather not add -1 to 2 because 1 is less than 2
            sSum[i]=Math.max(sSum[i-1],Math.max(sSum[i-1]+a[i],a[i]));//sparse sum, increase or keep the same
            cSum=Math.max(cSum+a[i],a[i]);//max sum ending here
            cSumMax = Math.max(cSumMax,cSum);//max so far is cSumMax
        }

        System.out.format("%d %d\n",cSumMax,sSum[a.length-1]);
    }

}