def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

function maxSubarray(arr) {
    let result = 0, subseq_sum = 0, subarr_sum = 0;
    arr.forEach((data) => {
        subseq_sum += data;
        if(data > 0) subarr_sum += data;

        if(result < subseq_sum) result = subseq_sum;
        if(subseq_sum < 0) subseq_sum =0;
    })
    
    if(result === 0) {
        return [Math.max(...arr), Math.max(...arr)];
    } else {
        return [result, subarr_sum];
    }
}

/*
denote dp[j] is the max sum of any sub-array in arr[0...j] ending at arr[j].

consider the sub-problem of dp[j]. how does it relate to dp[j-1]?

given dp[j-1], it corresponds to sum(arr[i*..j-1]) for some optimal i*
now consider tmp_j = sum(arr[p..j-1]) + arr[j].
find the p* such that the corresponding tmp_j* is the maximum over all p

the tmp_j consists of two parts, 
- the sum(arr[p..j-1]) part is obviously maximum when p = i*
- arr[j] part is fixed.

thus we only have to compare if
tmp_j = arr[j] is larger or
tmp_j = sum(arr[i*..j-1]) + arr[j] is larger.

we now can relate dp[j] to dp[j-1], as follow
dp[j] = max(arr[j], dp[j-1] + arr[j])

initially,
dp[-1] = 0 

the max sub-array in arr[0..N-1] is dp[j*] and j* can be found easily
by looking into the dp[0..N-1]. 

the max-sequence of arr[:] is simply the sum of all non-negative values of arry[:]. if all values are negative, max-sequence contains only the 
max value.
*/

vector<int> maxSubarray(vector<int> arr) {
    long dp = 0;
    long max_dp = numeric_limits<long>::min();
    long subseq = 0;
    long maxarrj = numeric_limits<long>::min();
    for (long arrj : arr) {
        dp = max(arrj, dp + arrj);
        max_dp = max(dp, max_dp);
        subseq += max(0l, arrj);
        maxarrj = max(maxarrj, arrj);
    }
    
    return {(int)max_dp, (int)(subseq>0? subseq: maxarrj)};
}

   /*
     The key to this one is that you want to do one pass through the data.  I first did a substring inner loop for the max subarray sum (code in comments), but this timed out for one test.
		 
            int subArraySum = 0;
            for (int j = i; j < arr.size(); j++) {
                subArraySum += arr.get(j);
                if (greatestSum == null || subArraySum > greatestSum) {
                    greatestSum = subArraySum;
                }
            }
        }
        results.add(greatestSum);
		 
    */
    public static List<Integer> maxSubarray2(List<Integer> arr) {
        List<Integer> results = new ArrayList<Integer>();            
        int subArraySum = 0;
        int sumSubSequence = 0;
        int subArraySumMax = 0;
        
        for (int i = 0; i < arr.size(); i++) {
            //this is to get the max subarray sum
            subArraySum += arr.get(i);
            if(subArraySum < 0) {
                subArraySum = 0;
            }
            subArraySumMax = Math.max(subArraySumMax, subArraySum);           

            //this is to get the max subsequence sum
            Integer value = arr.get(i);
            if (value > 0) {
                sumSubSequence += value;
            }
        }
        
        if (sumSubSequence > 0) {
            results.add(subArraySumMax);
            results.add(sumSubSequence);
        } else {
            //there are no positive values so we pick the highest value
            final int max = Collections.max(arr);
            results.add(max);
            results.add(max);
        }    
    
        return results;
    }