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
以上是 C ++中两个不重叠子数组的最大和 的全部内容， 来源链接： utcz.com/z/321565.html
