题目： 给定一个数组arr，其中有很多的子数组，找到两个不相容子数组使得相加的和最大，并返回和的最大值。比如，数组[1,-1,0,-2,3,5,-2,8,7,-4]，两个不相容子数组分别为[3,5]和[8,7]时累加和最大，所以返回23。再比如，数组[3,-1,0,-2,3,5,-2,8,7,-4]，两个不相容子数组分别为[3]和[3,5,-2,8,7]时累加和最大，所以返回24。 分析： 采用两个预处理数组。时间复杂度为O(N)，空间复杂度为O(N) left[i]用来表示arr[0..i]这个子数组最大累加和 right[i]用来表示arr[i..n-1]这个子数组的最大累加和 然后遍历一遍left[i]+right[i+1]的全局最大值即可
#include<iostream> #include<vector> #include<algorithm> #include<unordered_map> using namespace std; int maxSum(vector<int> &nums) { int len = nums.size(); vector<int>left(len); vector<int>right(len); left[0] = nums[0]; int sum = nums[0]; for (int i = 1; i < len; i++) { sum = sum > 0 ? sum + nums[i] : nums[i]; left[i] = max(left[i-1], sum); } left[len - 1] = nums[len - 1]; sum = nums[len - 1]; for (int i = len - 2; i >= 0; i--) { sum = sum > 0 ? sum + nums[i] : nums[i]; right[i] = max(right[i+1], sum); } int res = INT_MIN; for (int i = 0; i < len-1; i++) res = max(res, left[i] + right[i + 1]); return res; } int main() { vector<int>v = {3,-1,0,-3,3,5,-2,8,7,-4 }; vector<int>v1= {1, -1, 0, -2, 3, 5, -2, 8, 7, -4}; cout << maxSum(v1) << endl; }