C++での制約付きサブシーケンスの合計

numsと整数kという配列があるとすると、その配列の空でないサブシーケンスの最大合計を見つける必要があります。サブシーケンス内の2つの連続する数値ごとに、nums[i]とnums[j]となります。 i

ご存知のとおり、配列のサブシーケンスは、配列からいくつかの要素を削除し、残りの要素を元の順序のままにしておくことで取得されます。

したがって、入力が[10,2、-9,5,19]のようで、k =2の場合、サブシーケンスは[10,2,5,19]であるため、出力は36になります。

これを解決するには、次の手順に従います-

• ret：=-inf

• 配列dpを定義し、指定された配列をその中にコピーします

• 1つのdequedqを定義する

• dqの先頭にv[0]を挿入します

• n：=vのサイズ

• ret：=v [0]

• 初期化i：=1の場合、i

  • i> kであり、dqの最初の要素がdp [i --k --1]と同じである場合、

    • dqからフロント要素を削除します

  • dp [i]：=dp [i]の最大値および（dqが空の場合はdp [i] + 0、それ以外の場合はdp + dq [i]の最初の要素）

  • while（dqは空ではなく、dq

    • dqから最後の要素を削除する

  • dqの最後にdp[i]を挿入します

  • ret：=retとdp[i]

    の最大値

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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