C ++中的约束子序列总和

假设我们有一个名为nums的数组和一个整数k，我们必须找到该数组的一个非空子序列的最大和，以使子序列中每两个连续的数字nums [i]和nums [j]，其中i <j，条件j-i <= k为真。

众所周知，数组的子序列是通过从数组中删除一些元素而获得的，其余元素则保持其原始顺序。

因此，如果输入像[10,2，-9,5,19]且k = 2，则由于子序列为[10,2,5,19]，输出将为36。

为了解决这个问题，我们将遵循以下步骤-

• ret：= -inf

• 定义一个数组dp并将给定的数组复制到其中

• 定义一个双端队列dq

• 在dq的开头插入v [0]

• n：= v的大小

• ret：= v [0]

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• 从dq中删除最后一个元素

• 从dq中删除前元素

• 如果i> k并且dq的第一个元素与dp [i-k-1]相同，则

• dp [i]：= dp [i]的最大值，并且（如果dq为空，则dp [i] + 0，否则为dp + dq [i]的第一个元素）

• 而（不是dq为空，并且dq的最后一个元素<dp [i]），则执行-

• 在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