最大サブ配列II-LIntCode

整数配列を指定し、重複しない2つのサブ配列を見つけて、それらの和を最大にします.各サブ配列の数値は、配列内の位置が連続しているはずです.最大の和を返します.

サンプルは、配列[1,3,−1,2,−1,2]の2つのサブ配列がそれぞれ[1,3]および[2,−1,2]または[1,3,−1,2]および[2]であり、それらの最大和はいずれも7である.
チャレンジ要求時間複雑度O(n)
構想は配列を2つのサブ配列に分けるため、nums[0]からnums[i]までの配列、そのサブ配列の和の最大値をleft[i]で表すことができる.right[j]はnums[j]からnums[len-1]までの配列を表し、そのサブ配列和の最大値を表す.最終的な結果はleft[k]+right[k+1]の最大値である.

#ifndef C42_H
#define C42_H
#include
#include
using namespace std;
class Solution {
public:
    int maxTwoSubArrays(vector<int> nums) {
        int res1 =INT_MIN, res2 = INT_MIN;
        int Max = INT_MIN;
        int tmp1 = 0, tmp2 = 0;
        int len = nums.size();
        vector<int> left(len, 0);
        vector<int> right(len, 0);
        //left[i]  nums[0] nums[i]     ,         
        for (int i = 0; iif (tmp1<0)
                tmp1 = 0;
            tmp1 += nums[i];
            res1 = maxVal(res1, tmp1);
            left[i] = res1;
        }
        //right[j]  nums[j] nums[len-1]     ,         
        for (int j = len - 1; j >= 0; --j)
        {
            if (tmp2<0)
                tmp2 = 0;
            tmp2 += nums[j];
            res2 = maxVal(res2, tmp2);
            right[j] = res2;
        }
        //           
        for (int k = 0; k1; ++k)
        {
            Max = maxVal(Max, left[k] + right[k + 1]);
        }
        return Max;
    }
    int maxVal(int a, int b)
    {
        return a>b ? a : b;
    }
};
#endif