정수 배열 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
-
0 <=j
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=A의 크기
-
크기 n의 배열 leftL 정의, 크기 n의 배열 leftM 정의
-
크기 n의 배열 rightL 정의, 크기 n의 배열 rightM 정의
-
ret :=0, temp :=0
-
i를 초기화하기 위해 :=0, i
-
온도 =온도 + A[i]
-
-
초기화 i :=L, j :=0, i
-
leftL[i − 1] :=temp 및 x의 최대값 여기서 x는 i − 2 <0일 때 0이고 그렇지 않으면 x =leftL[i − 2]
-
온도 =온도 + A[i]
-
온도 =온도 - A[j]
-
-
leftL[n − 1] :=최대 온도, x 여기서 n − 2 <0일 때 x는 0, 그렇지 않으면 x :=leftL[n − 2]
-
온도 :=0
-
i를 초기화하기 위해 :=0, i
-
온도 =온도 + A[i]
-
-
초기화 i :=M, j :=0, i
-
온도 =온도 + A[i]
-
온도 =온도 - A[j]
-
-
leftM[n − 1] :=temp 및 x의 최대값 x 일 때 :=n - 2 <0이면 0, 그렇지 않으면 x :=leftM[n − 2]
-
온도 :=0
-
i :=n − 1 초기화를 위해 i> n − 1 − L일 때 i 1 do −
감소-
온도 =온도 + A[i]
-
-
i :=n − 1 − L, j :=n − 1 초기화를 위해 i>=0일 때 i를 1만큼 감소시키고 j를 1만큼 감소시키고 −
-
rightL[i + 1] :=온도 및 x의 최대값, 여기서 x는 i + 2>=n이면 0이고 그렇지 않으면 x =rightL[i + 2]
-
온도 =온도 + A[i]
-
온도 =온도 - A[j]
-
-
rightL[0] :=최대 온도 및 rightL[1]
-
온도 :=0
-
i :=n − 1 초기화를 위해 i> n − 1 − M일 때 i 1 do −
감소-
온도 =온도 + A[i]
-
-
i :=n − 1 − M, j :=n − 1을 초기화하기 위해 i>=0일 때 i를 1만큼 감소시키고 j를 1만큼 감소시키고 −
-
rightM[i + 1] :=temp 및 x의 최대값, 여기서 x는 i + 2일 때 0>=n, 그렇지 않으면 x :=rightM[i + 2]
-
온도 =온도 + A[i]
-
온도 =온도 - A[j]
-
-
rightM[0] :=최대 온도 및 rightM[1]
-
i :=L − 1 초기화를 위해 i <=n − 1 − M일 때 i를 1 do −
증가-
ret :=ret 및 leftL[i] + rightM[i + 1]
의 최대값
-
-
i :=M − 1 초기화를 위해 i <=n − 1 − L일 때 i를 1 do −
증가-
ret :=ret 및 leftM[i] + rightL[i + 1]
의 최대값
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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