给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。 每个子数组的数字在数组中的位置应该是连续的。 返回最大的和。
样例 例1: 输入: [1, 3, -1, 2, -1, 2] 输出: 7 解释: 最大的子数组为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]. 例2: 输入: [5,4] 输出: 9 解释: 最大的子数组为 [5] 和 [4]. 挑战 要求时间复杂度为 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<int> &nums) { // write your code here const unsigned len = nums.size(); int *a = new int[len]; int *b = new int[len]; int lsum = 0, rsum = 0, maxs = nums[0]; for (int i = 0; i < len; i++) { /* code */ lsum=lsum<0?0:lsum; lsum += nums[i]; maxs = max(maxs, lsum); a[i] = maxs; } maxs = nums[nums.size() - 1]; for (int i = len - 1; i >= 0; i--) { /* code */ rsum=rsum<0?0:rsum; rsum += nums[i]; maxs = max(maxs, rsum); b[i] = maxs; } maxs = a[0] + b[1]; for (int i = 1; i < len-1; i++) {//不管区间段，只管最大值 /* code */ //int temp= maxs = max(maxs, a[i] + b[i + 1]); } delete[]a; delete[]b; return maxs; } };