Maximum Subarray II

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

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
        if (nums.size() < 2) {
            return 0;
        }
        int len = nums.size();
        vector<int> temp(len, INT_MIN);
        vector<int> forward(len, INT_MIN);
        vector<int> backward(len, INT_MIN);
        // forward, get max subarray by index i
        temp[0] = nums[0];
        forward[0] = nums[0];
        for (int i = 1; i < len; ++i) {
            temp[i] = max(temp[i-1] + nums[i], nums[i]);
            forward[i] = max(forward[i-1], temp[i]);
        }
        // backward, get max subarray after i-1
        temp.clear();
        temp.resize(len + 1, INT_MIN);
        temp[len-1] = nums[len-1];
        backward[len-1] = nums[len-1];
        for (int i = len - 2; i >= 0; --i) {
            temp[i] = max(temp[i+1] + nums[i], nums[i]);
            backward[i] = max(backward[i+1], temp[i]);
        }
        // find what we need
        int result = INT_MIN;
        for (int i = 0; i < len - 1; ++i) {
            result = max(result, forward[i] + backward[i+1]);
        }
        // for (int i = 0; i < len; ++i) {
        //     cout << forward[i] << " ";
        // }
        // cout << endl << "--------------" << endl;
        // for (int i = 0; i < len; ++i) {
        //     cout << backward[i] << " ";
        // }
        // cout << endl << "--------------" << endl;
        return result;
    }
};

Similar problems

x

Tags

x