Giả sử chúng ta có một mảng A gồm các số nguyên; chúng ta phải tìm tổng lớn nhất của các phần tử trong hai mảng con không trùng nhau. Độ dài của các mảng con này là L và M.
Vì vậy, chính xác hơn chúng ta có thể nói rằng, chúng ta phải tìm V lớn nhất mà
V =(A [i] + A [i + 1] + ... + A [i + L-1]) + (A [j] + A [j + 1] + ... + A [j + M-1]) và một trong hai -
-
0 <=i
-
0 <=j
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của A
-
Xác định mảng leftL có kích thước n, Xác định mảng leftM có kích thước n
-
Xác định mảng rightL có kích thước n, Xác định một mảng rightM có kích thước n
-
ret:=0, temp:=0
-
để khởi tạo i:=0, khi i
-
temp =temp + A [i]
-
-
để khởi tạo i:=L, j:=0, khi i
-
leftL [i - 1]:=max of temp và x trong đó x là 0 khi i - 2 <0, ngược lại x =leftL [i - 2]
-
temp =temp + A [i]
-
temp =temp - A [j]
-
-
leftL [n - 1]:=max của nhiệt độ và x trong đó x là 0 khi n - 2 <0, ngược lại x:=leftL [n - 2]
-
tạm thời:=0
-
để khởi tạo i:=0, khi i
-
temp =temp + A [i]
-
-
để khởi tạo i:=M, j:=0, khi i
-
temp =temp + A [i]
-
temp =temp - A [j]
-
-
leftM [n - 1]:=max của nhiệt độ và x khi x:=0 nếu n - 2 <0 nếu không x:=leftM [n - 2]
-
tạm thời:=0
-
để khởi tạo i:=n - 1, khi i> n - 1 - L, giảm i đi 1 do -
-
temp =temp + A [i]
-
-
để khởi tạo i:=n - 1 - L, j:=n - 1, khi i> =0, giảm i đi 1, giảm j đi 1, do -
-
rightL [i + 1]:=max of temp và x trong đó x là 0 nếu i + 2> =n ngược lại x =rightL [i + 2]
-
temp =temp + A [i]
-
temp =temp - A [j]
-
-
rightL [0]:=max of temp và rightL [1]
-
tạm thời:=0
-
để khởi tạo i:=n - 1, khi i> n - 1 - M, giảm i đi 1 do -
-
temp =temp + A [i]
-
-
để khởi tạo i:=n - 1 - M, j:=n - 1, khi i> =0, giảm i đi 1, giảm j đi 1, do -
-
rightM [i + 1]:=max của temp và x, trong đó x là 0 khi i + 2> =n ngược lại x:=rightM [i + 2]
-
temp =temp + A [i]
-
temp =temp - A [j]
-
-
rightM [0]:=max of temp và rightM [1]
-
để khởi tạo i:=L - 1, khi i <=n - 1 - M, tăng i lên 1 do -
-
ret:=max của ret và leftL [i] + rightM [i + 1]
-
-
để khởi tạo i:=M - 1, khi i <=n - 1 - L, hãy tăng i lên 1 do -
-
ret:=max of ret và leftM [i] + rightL [i + 1]
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[0,6,5,2,3,5,1,9,4] 1 2
Đầu ra
20