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