nums라는 배열과 정수 k가 있다고 가정하면 해당 배열의 비어 있지 않은 부분 시퀀스의 최대 합을 찾아야 하므로 부분 시퀀스의 모든 두 개의 연속 숫자 nums[i] 및 nums[j], 여기서 i
우리가 알고 있듯이 배열의 하위 시퀀스는 배열에서 일부 요소를 삭제하고 나머지 요소는 원래 순서대로 남겨둠으로써 얻습니다.
따라서 입력이 [10,2,-9,5,19]이고 k =2인 경우 하위 시퀀스가 [10,2,5,19]이므로 출력은 36이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret :=-inf
-
배열 dp를 정의하고 주어진 배열을 복사합니다.
-
하나의 데크 dq 정의
-
dq의 시작 부분에 v[0] 삽입
-
n :=v의 크기
-
ret :=v[0]
-
initialize i :=1의 경우 i
-
i> k이고 dq의 첫 번째 요소가 dp[i - k - 1]과 같으면
-
dq에서 앞 요소 삭제
-
-
dp[i] :=dp[i]의 최대값 및 (dq가 비어 있으면 dp[i] + 0, 그렇지 않으면 dp + dq[i]의 첫 번째 요소)
-
동안(dq가 비어 있지 않고 dq
-
dq에서 마지막 요소 삭제
-
-
dq의 끝에 dp[i] 삽입
-
ret :=ret 및 dp[i]
의 최대값
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h> using namespace std; const int inf = 1e9 + 10; class Solution { public: int constrainedSubsetSum(vector<int>& v, int k) { int ret = -inf; vector<int> dp(v.begin(), v.end()); deque<int> dq; dq.push_front(v[0]); int n = v.size(); ret = v[0]; for (int i = 1; i < n; i++) { if (i > k && dq.front() == dp[i - k - 1]) dq.pop_front(); dp[i] = max(dp[i], dq.empty() ? dp[i] + 0 : dp[i] + dq.front()); while (!dq.empty() && dq.back() < dp[i]) dq.pop_back(); dq.push_back(dp[i]); ret = max(ret, dp[i]); } return ret; } }; main(){ Solution ob; vector<int> v = {10,2,-9,5,19}; cout << (ob.constrainedSubsetSum(v, 2)); }
입력
{10,2,-9,5,19}, 2
출력
36