C ++中两个不重叠子数组的最大和
假设我们有一个整数数组A；我们必须找到两个不重叠的子数组中元素的最大和。这些子阵列的长度为L和M。
因此，更确切地说，我们必须找到最大的V
V=（A[i]+A[i+1]+...+A[i+L-1]）+（A[j]+A[j+1]+...+A[j+M-1]），然后-
0<=i<i+L−1<j<j+M−1<A的大小
0<=j<j+M−1<i<i+L−1<A的大小
为了解决这个问题，我们将遵循以下步骤-
n：=A的大小
定义大小为n的leftL数组，定义大小为n的leftM数组
定义大小为n的数组rightL，定义大小为n的数组rightM
ret：=0，温度：=0
用于初始化i：=0，当i<L时，将i增加1做-
温度=温度+A[i]
为了初始化i：=L，j：=0，当i<n时，将i增加1，将j增加1，执行-
leftL[i-1]：=温度和x的最大值，当i-2<0时x为0，否则x=leftL[i-2]
温度=温度+A[i]
temp=temp−A[j]
leftL[n−1]：=温度的最大值，当n−2<0时x为0，否则x：=leftL[n−2]
温度：=0
用于初始化i：=0，当i<M时，将i增加1做-
温度=温度+A[i]
为了初始化i：=M，j：=0，当i<n时，将i增加1，将j增加1，执行-
温度=温度+A[i]
temp=temp-A[j]
leftM[n−1]：=温度和x的最大值，如果x：=0，则n-2<0，否则x：=leftM[n−2]
温度：=0
用于初始化i：=n−1，当i>n−1−L时，将i减1做-
温度=温度+A[i]
为了初始化i：=n-1-L，j：=n-1，当i>=0时，将i减1，将j减1，执行-
rightL[i+1]：=温度和x的最大值，如果i+2>=n，则x为0，否则x=rightL[i+2]
温度=温度+A[i]
temp=temp−A[j]
rightL[0]：=温度和rightL[1]的最大值
温度：=0
用于初始化i：=n−1，当i>n−1−M时，将i减1做-
温度=温度+A[i]
为了初始化i：=n-1-M，j：=n-1，当i>=0时，将i减1，将j减1，执行-
rightM[i+1]：=温度和x的最大值，其中当i+2>=n时x为0，否则x：=rightM[i+2]
温度=温度+A[i]
temp=temp−A[j]
rightM[0]：=温度和rightM[1]的最大值
用于初始化i：=L−1，当i<=n−1-M时，将i加1做-
ret：=ret和leftL[i]+rightM[i+1]的最大值
用于初始化i：=M−1，当i<=n−1-L时，将i加1做-
ret：=ret和leftM[i]+rightL[i+1]的最大值
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
int n = A.size();
vector <int> leftL(n);
vector <int> leftM(n);
vector <int> rightL(n);
vector <int> rightM(n);
int ret = 0;
int temp = 0;
for(int i = 0; i < L; i++){
temp += A[i];
}
for(int i = L, j = 0; i < n; i++, j++){
leftL[i − 1] = max(temp, i − 2 < 0 ? 0 : leftL[i − 2]);
temp += A[i];
temp −= A[j];
}
leftL[n − 1] = max(temp, n − 2 < 0 ? 0 : leftL[n − 2]);
temp = 0;
for(int i = 0; i < M; i++){
temp += A[i];
}
for(int i = M, j = 0; i < n; i++, j++){
leftM[i − 1] = max(temp, i − 2 < 0 ? 0 : leftM[i − 2]);
temp += A[i];
temp −= A[j];
}
leftM[n − 1] = max(temp, n − 2 < 0 ? 0 : leftM[n − 2]);
//out(leftM);
temp = 0;
for(int i = n − 1; i > n − 1 − L; i−−){
temp += A[i];
}
for(int i = n − 1 − L, j = n − 1; i >= 0 ; i−−, j−− ){
rightL[i + 1] = max(temp, (i + 2 >= n ? 0 : rightL[i + 2]));
temp += A[i];
temp −= A[j];
}
rightL[0] = max(temp, rightL[1]);
temp = 0;
for(int i = n − 1; i > n − 1 − M; i−−){
temp += A[i];
}
for(int i = n − 1 − M, j = n − 1; i >= 0 ; i−−, j−− ){
rightM[i + 1] = max(temp, (i + 2 >= n ? 0 : rightM[i + 2]));
temp += A[i];
temp −= A[j];
}
rightM[0] = max(temp, rightM[1]);
for(int i = L − 1; i <= n − 1 − M; i++){
ret = max(ret, leftL[i] + rightM[i + 1]);
}
for(int i = M − 1; i <= n − 1 − L; i++){
ret = max(ret, leftM[i] + rightL[i + 1]);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v1 = {0,6,5,2,3,5,1,9,4};
cout << (ob.maxSumTwoNoOverlap(v1, 1, 2));
}输入值
[0,6,5,2,3,5,1,9,4] 1 2
输出结果
20