假设我们有一个名为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