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