Maximum Subarray II Show result

Given an array of integers, find two non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

Have you met this question in a real interview? 

Yes

Example

For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or[1, 3, -1, 2] and [2], they both have the largest sum 7.

Note

The subarray should contain at least one number

Challenge

Can you do it in time complexity O(n) ?

public class Solution {

    /**

     * @param nums: A list of integers

     * @return: An integer denotes the sum of max two non-overlapping subarrays

     */

    public int maxTwoSubArrays(ArrayList<Integer> nums) {

        // write your code

        int n = nums.size();

        int[] maxLR = new int[n];

        int[] maxRL = new int[n];

        maxLR[0] = nums.get(0);

        int pre = nums.get(0);

        for(int i = 1; i < n; i++){

            int sum = nums.get(i) + (pre > 0 ? pre : 0);

            pre = sum;

            maxLR[i] = Math.max(maxLR[i-1], sum);

        }

        

        maxRL[n-1] = nums.get(n-1);

        pre = nums.get(n-1);

        for(int i = n-2; i >= 0; i--){

            int sum = nums.get(i) + (pre > 0 ? pre : 0);

            pre = sum;

            maxRL[i] = Math.max(maxRL[i+1], sum);

        }

        

        int maxSum = Integer.MIN_VALUE;

        for(int i = 0; i < n-1; i++){

            maxSum = Math.max(maxSum, maxRL[i+1] + maxLR[i]);

            

        }

        

        return maxSum;

    }

}