C++의 제한된 부분 시퀀스 합

<시간/>

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