1031. 两个非重叠子数组的最大和
关键词：前缀和
题目起源：1031. 两个非重叠子数组的最大和 - 力扣（Leetcode）
题目形容
T前缀和给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度别离为 firstLen 和 secondLen 。
长度为 firstLen 的子数组能够呈现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。
子数组是数组的一个 间断 局部。
输出：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2输入：20解释：子数组的一种抉择中，[9] 长度为 1，[6,5] 长度为 2。输出：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2输入：29解释：子数组的一种抉择中，[3,8,1] 长度为 3，[8,9] 长度为 2。输出：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3输入：31解释：子数组的一种抉择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。数据范畴1 <= firstLen, secondLen <= 10002 <= firstLen + secondLen <= 1000firstLen + secondLen <= nums.length <= 10000 <= nums[i] <= 1000问题剖析
两个不重叠子数组必然位于某条分界线的两侧，于是，无妨枚举每条分界线，设其左侧子数组的最大值为l，右侧子数组的最大值为r，则，max{ l+r }即为答案。
如何疾速晓得分界线左/右侧的最大值呢？无妨先思考长度为 firstLen 的子数组能够呈现在长为 secondLen 的子数组之前的状况。因为子数组长度已知，且子数组间断，于是可采纳一遍扫描，窗口一直向右/左滑动，预处理出所有分界线左/右侧的子数组的最大值。
当长度为 firstLen 的子数组在之后时，求解过程完全相同，于是，无妨上述求解过程封装成一个函数，将前后数组的长度作为参数。
为了不便计算指定区间元素和，可先预处理出前缀和。
工夫复杂度：O(n)
空间复杂度：O(n)
代码实现
int maxSumTwoNoOverlap_2(vector<int> &nums, int firstLen, int secondLen) { // pre[i]示意[1..i]中指定长度的子数组的最大值 int n = nums.size(), pre[n+1]; // 前缀和 for (int i = 1; i < n; i++)nums[i] += nums[i - 1]; // 抽取公共局部 auto f = [&](int s, int t) { int res = 0; // [1..i]中长度为s的子数组的最大值 pre[s] = nums[s - 1]; for (int i = s + 1; i <= n; i++) pre[i] = max(nums[i - 1] - nums[i - 1 - s], pre[i - 1]); // [i+1..n]中长度为t的子数组的最大值 for (int i = n - t, curMax = 0; i >= s; i--) { curMax = max(nums[i + t - 1] - nums[i - 1], curMax); res = max(pre[i] + curMax, res); } return res; }; return max(f(firstLen, secondLen), f(secondLen, firstLen));}