C ++中3个非重叠子数组的最大和
假设我们有一个称为正整数的数组，我们必须找到三个具有最大和的非重叠子数组。在这里，每个子数组的大小为k，我们希望最大化所有3*k项的总和。
我们必须以代表每个间隔的开始位置的索引列表的形式找到结果。如果有多个答案，我们将返回字典上最小的答案。
因此，如果输入像[1,2,1,2,6,8,4,1]且k=2，则结果将为[0,3,5]，因此子数组为[1,2]，[2,6]，[8,4]对应于起始索引[0,3,5]。
为了解决这个问题，我们将遵循以下步骤-
n：=nums的大小
定义大小为3的数组ret用inf填充
定义大小为n+1的数组和
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
sum[i+1]=sum[i]+nums[i]
定义大小为n的数组posLeft
定义大小为n的posRight数组，用n-k填充
对于初始化i：=k，currMax：=sum[k]-sum[0]，当i<n时，更新（将i增加1），执行-
posLeft[i]：=posLeft[i-1]
currMax：=newTotal
posLeft[i]：=i+1-k
newTotal：=sum[i+1]-sum[i+1-k]
如果newTotal>currMax，则-
除此以外
对于初始化i：=n-k-1，currMax：=sum[n]-sum[n-k]，当i>=0时，更新（将i减1），-
posRight[i]：=posRight[i+1]
currMax：=newTotal
posRight[i]：=i
newTotal：=sum[i+k]-sum[i]
如果newTotal>=currMax，则-
除此以外
要求：=0
对于初始化i：=k，当i<=n-2*k时，更新（将i增加1），执行-
ret[0]：=l，ret[1]：=i，ret[2]：=r
req：=临时
l：=posLeft[i-1]，r：=posRight[i+k]
温度：=（sum[l+k]-sum[l]）+（sum[i+k]-sum[i]）+（sum[r+k]-sum[r]）
如果temp>req，则-
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector <int> ret(3, INT_MAX);
vector <int> sum(n + 1);
for(int i = 0; i < n; i++){
sum[i + 1] = sum[i] + nums[i];
}
vector <int> posLeft(n);
vector <int> posRight(n, n - k);
for(int i = k, currMax = sum[k] - sum[0]; i < n; i++){
int newTotal = sum[i + 1] - sum[i + 1- k];
if(newTotal > currMax){
currMax = newTotal;
posLeft[i] = i + 1 - k;
}else{
posLeft[i] = posLeft[i - 1];
}
}
for(int i = n - k - 1, currMax = sum[n] - sum[n - k]; i >=0 ; i--){
int newTotal = sum[i + k] - sum[i];
if(newTotal >= currMax){
currMax = newTotal;
posRight[i] = i;
}else{
posRight[i] = posRight[i + 1];
}
}
int req = 0;
for(int i = k; i <= n - 2 * k; i++){
int l = posLeft[i - 1];
int r = posRight[i + k];
int temp = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]);
if(temp > req){
ret[0] = l;
ret[1] = i;
ret[2] = r;
req = temp;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,2,6,8,4,1};
print_vector(ob.maxSumOfThreeSubarrays(v, 2));
}输入值
{1,2,1,2,6,8,4,1}
2输出结果
[0, 3, 5, ]