最大およびサブ配列2


整数配列を指定し、重複しない2つのサブ配列を見つけて、それらの和を最大にします.各サブ配列の数値は、配列内の位置が連続しているはずです.最大の和を返します.
注意事項
サブ配列には最低1つの数が含まれます
実際の面接でこの問題に遭遇したことがありますか?
Yes
サンプル
配列[1, 3, -1, 2, -1, 2]の2つのサブ配列は、それぞれ[1, 3]および[2, -1, 2]または[1, 3, -1, 2]および[2]であり、それらの最大および平均は7である.
に挑戦
要求時間複雑度O(n)
ポイント:左から右と右から左
class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector &nums) {
        // write your code here
        if (nums.size() == 0) {
            return 0;
        }
        int cur_sum = 0;
        int max_sum = nums[0];
        vector left(nums.size(), 0);
        vector right(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++) {
            cur_sum = max(cur_sum + nums[i], nums[i]);
            max_sum = max(cur_sum, max_sum);
            left[i] = max_sum;
        }
        cur_sum = 0;
        max_sum = nums[nums.size() - 1];
        for (int j = nums.size() - 1; j >= 0; j--) {
            cur_sum = max(cur_sum + nums[j], nums[j]);
            max_sum = max(cur_sum, max_sum);
            right[j] = max_sum;
        }
        max_sum = INT_MIN;
        for (int k = 0; k < nums.size() - 1; k++) {
            max_sum = max(max_sum, left[k] + right[k + 1]);
        }
        return max_sum;
    }
};