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