Maximum Subarray II

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

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

Key Points: O(2n/3n), O(2n)

1. Two ways: DP / Prefix Sum (Same time/space complexity)
2. initialize leftMax[] / rightMax[] (Can be done in one loop)
3. Follow the formula

 public int maxTwoSubArrays(ArrayList<Integer> nums) {
        if(nums.size()==0){return 0;}

        int len = nums.size();
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];

        // compute leftMax
        leftMax[0] =nums.get(0);
        int lastResult = nums.get(0);
        for(int i=1; i<len; i++){
            int curr = nums.get(i);
            lastResult=Math.max(curr,curr+lastResult);
            leftMax[i]=Math.max(lastResult,leftMax[i-1]);
        }


        // compute rightMax
        rightMax[len-1] =nums.get(len-1);
        lastResult = nums.get(len-1);
        for(int i=len-2; i>=0; i--){
            int curr = nums.get(i);
            lastResult =Math.max(curr,curr+lastResult);
            rightMax[i]=Math.max(lastResult,rightMax[i+1]);
        }

        // merge the result 
        int max = Integer.MIN_VALUE;
        for(int i=0; i<len-1;i++){
            max = Math.max(max,leftMax[i]+rightMax[i+1]);
        }

        return max;
    }