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.

http://www.lintcode.com/en/problem/maximum-subarray-difference/

Discussion

还是Maximum Subarray问题的思想，只是扩展了

1. 从左到右求最大，从右到左求最小
2. 从左到右求最小，从右到左求最大

刚开始忽略的第二种情况。

Solution

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) {
        // write your code here
        int n = nums.size();
        if(n < 1) return 0;
        vector<int> maxlocal(n);//from left to right, max
        vector<int> minlocal(n); //from right to left, min
        maxlocal[0] = nums[0];
        for(int i=1; i<n; i++) {
            maxlocal[i] = max(nums[i], nums[i]+maxlocal[i-1]);
        }
        minlocal[n-1] = nums[n-1];
        for(int i=n-2; i>=0; i--) {
            minlocal[i] = min(nums[i], nums[i]+minlocal[i+1]);
        }

        vector<int> minlocalLR(n); //from letto right, min
        minlocalLR[0] = nums[0];
        for(int i=1; i<n; i++) {
            minlocalLR[i] = min(nums[i], nums[i]+minlocalLR[i-1]);
        }

        vector<int> maxlocalRL(n); //from right to left, max
        maxlocalRL[n-1] = nums[n-1];
        for(int i=n-2; i>=0; i--) {
            maxlocalRL[i] = max(nums[i], nums[i]+maxlocalRL[i+1]);
        }

        int result = INT_MIN;
        for(int i=0; i<n-1; i++) {
            result = max(result, abs(maxlocal[i] - minlocal[i+1]));
            result = max(result, abs(maxlocalRL[i+1] - minlocalLR[i]));
        }
        return result;
    }
};