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.

分析：

这题目的逻辑很麻烦，并不只是单纯的forward-backward，这道题目其实是double forward-backward。有两种可能性，前小后大，还有前大后小。

解法：

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) {
        // I decide forward is max, backward is min
        int sum1 = 0;
        int sum2 = 0;
        int maxSum = INT_MIN;
        int minSum = INT_MAX;
        vector<int> forwardMax(nums.size(), INT_MIN);
        vector<int> forwardMin(nums.size(), INT_MAX);
        for (int i = 0; i < nums.size(); i++) {
            sum1 += nums[i];
            maxSum = max(maxSum, sum1);
            forwardMax[i] = maxSum;
            sum1 = max(sum1, 0);

            sum2 += nums[i];
            minSum = min(minSum, sum2);
            forwardMin[i] = minSum;
            sum2 = min(sum2, 0);
        }

        sum1 = 0;
        sum2 = 0;
        maxSum = INT_MIN;
        minSum = INT_MAX;
        vector<int> backwardMax(nums.size(), INT_MIN);
        vector<int> backwardMin(nums.size(), INT_MAX);
        for (int j = nums.size() - 1; j >= 0; j--) {
            sum1 += nums[j];
            maxSum = max(maxSum, sum1);
            backwardMax[j] = maxSum;
            sum1 = max(sum1, 0);

            sum2 += nums[j];
            minSum = min(minSum, sum2);
            backwardMin[j] = minSum;
            sum2 = min(sum2, 0);
        }

        int sumForward = INT_MIN; 
        int sumBackward = INT_MIN; 
        // now let sum be the non-overlapping difference
        for (int i = 0; i < nums.size() - 1; i++) {
            sumForward = max(sumForward, forwardMax[i] - backwardMin[i + 1]);
            sumBackward = max(sumBackward, backwardMax[i + 1] - forwardMin[i]);
        }
        return max(sumForward, sumBackward);
    }
};