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.

接口：

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> nums) {
        // write your code here

    }
};

分析：

首先，很明显的，这题目要求non-overlapping subarray，所以说应该是forward-backward traversal的一个典型应用。在了解maximum subarray的基础上题目应该并不难，只要别写bug就妥帖。

在这里想强调一件事，forward-backward traversal的时候，最后一次求最大值需要思考一下每个vector的含义。一般情况下从0循环到倒数第二个数，并且循环体中用(forward[i] + backward[i + 1])。只有当做profit的时候，vector的一端为0，才可以循环到底。

解法：

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> nums) {
        // write your code here
        int sum = 0;
        int maxSum = INT_MIN;
        vector<int> forward(nums.size(), INT_MIN);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            maxSum = max(maxSum, sum);
            forward[i] = maxSum;
            sum = max(sum, 0);
        }
        sum = 0;
        maxSum = INT_MIN;
        vector<int> backward(nums.size(), INT_MIN);
        for (int j = nums.size() - 1; j >= 0; j--) {
            sum += nums[j];
            maxSum = max(maxSum, sum);
            backward[j] = maxSum;
            sum = max(sum, 0);
        }
        maxSum = INT_MIN;
        for (int i = 0; i < nums.size() - 1; i++) {
            maxSum = max(maxSum, forward[i] + backward[i + 1]);
        }
        return maxSum;
    }
};