本文主要是介绍不相容子数组的最大和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
给定一个数组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;
}这篇关于不相容子数组的最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
