LintCode: Maximum Subarray Difference

Given an array with integers.
Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.
Return the largest difference.

Note

The subarray should contain at least one number

Example

For [1, 2, -3, 1], return 6

 
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two
     *          Subarrays
     */
    int maxDiffSubArrays(vector<int> nums) {
        int n = nums.size();
        vector<int> maxLR(n, nums[0]);
        vector<int> maxRL(n, nums[n-1]);
        vector<int> minLR(n, nums[0]);
        vector<int> minRL(n,  nums[n-1]);
        
        int prev = nums[0];
        for(int i = 1; i< n; i++){
           int sum = nums[i] + (prev > 0? prev : 0);
           prev = sum;
           maxLR[i] = max(sum, maxLR[i-1]);
        }
        
        prev = nums[0];
        for(int i = 1; i< n; i++) 
        {
           int sum = nums[i] + (prev < 0? prev: 0);
           prev = sum;
           minLR[i] = min(sum, minLR[i-1]);
        }
        
        prev = nums[n-1];
        for(int i = n-2; i>=0; i--) 
        {
            int sum = nums[i] + (prev > 0 ? prev : 0);
            prev = sum;
            maxRL[i] = max(sum, maxRL[i+1]);
        }
        
        prev = nums[n-1];
        for(int i = n-2; i>=0; i--)
        {
           int sum = nums[i] +(prev < 0? prev: 0);    
           prev = sum;
           minRL[i] = min(sum, minRL[i+1]);   
        }
          
        int dif = INT_MIN;
        for(int i = 0; i < n-1; i++)
           dif = max(dif, abs(maxLR[i]-minRL[i+1]));
        for(int i = n-1; i>0; i--)
           dif = max(dif, abs(maxRL[i]-minLR[i-1]));
        return dif; 
    }
};