lintcode-medium-Maximum Subarray II

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
        
        if(nums == null || nums.size() == 0)
            return 0;
        
        int size = nums.size();
        
        int sum = nums.get(0);
        int[] l2r = new int[size];
        int[] r2l = new int[size];
        l2r[0] = nums.get(0);
        r2l[size - 1] = nums.get(size - 1);
        
        for(int i = 1; i < size; i++){
            if(sum < 0)
                sum = 0;
            
            sum += nums.get(i);
            
            if(sum > l2r[i - 1])
                l2r[i] = sum;
            else
                l2r[i] = l2r[i - 1];
        }
        
        sum = nums.get(size - 1);
        
        for(int i = size - 2; i >= 0; i--){
            if(sum < 0)
                sum = 0;
            
            sum += nums.get(i);
            
            if(sum > r2l[i + 1])
                r2l[i] = sum;
            else
                r2l[i] = r2l[i + 1];
        }
        
        int result = Integer.MIN_VALUE;
        
        for(int i = 0; i < size - 1; i++)
            result = Math.max(result, l2r[i] + r2l[i + 1]);
        
        return result;
    }
}