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.

Can you do it in time complexity O(n) ?

For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.

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

Discussion

利用Maximum Subarry的思想，给定任意位置，我都计算一个左右两边的max的和，这样是O(n^2) runtime, 结果提交的时候发现超时了。。。。

Solution

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 n= nums.size();
        if(n == 0) return -1;
        int result = INT_MIN;
        for(int i=0; i<n-1; i++) {
            int left = maxOneSubArray(nums, 0, i);
            int right = maxOneSubArray(nums, i+1, n-1);
            if(left+right > result)
                result = left+right;
        }
        return result;

    }
private:
    int maxOneSubArray(vector<int> nums, int start, int end) {
        int result = nums[start];
        for(int i=start+1; i<=end; i++) {
            nums[i] = max(nums[i], nums[i]+nums[i-1]);
            if(nums[i] > result) {
                result = nums[i];
            }
        }
        return result;
    }
};

Follow up

计算一个从左到右的最大值，和一个从右道左的最大值。然后再选出两个不重叠的子数组和最大的情况。

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) {
        if(nums.empty()) return 0;
        int n = nums.size();
        //1. compute max sum in [0`i], save in max_left
        vector<int> max_from_left(n, INT_MIN);
        int local = 0;
        int global = INT_MIN;
        for(int i=0; i<n; i++) {
            global = max(global, local+nums[i]);
            local = max(0, local+nums[i]);
            max_from_left[i] = global;
        }
         //2. compute max sum in [i~n-1], save in max_right
        local = 0;
        global = INT_MIN;
        vector<int> max_from_right(n, INT_MIN);
        for(int i=n-1; i>=0; i--) {
            global = max(global, local+nums[i]);
            local = max(0, local+nums[i]);
            max_from_right[i] = global;
        }
        //3. find the two subarrays
        int result = INT_MIN;
        for(int i=0; i<n-1; i++) {
            result = max(result, max_from_left[i] + max_from_right[i+1]);
        }
        return result;
    }
};