数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的受约束子序列和
假设我们有一个名为 nums 的数组和一个整数 k，我们需要找到该数组的非空子序列的最大和，使得对于子序列中每两个连续的数字 nums[i] 和 nums[j]，其中 i < j，条件 j - i <= k 为真。
众所周知，数组的子序列是通过从数组中删除一些元素获得的，并将剩余的元素按其原始顺序保留。
因此，如果输入类似于 [10, 2, -9, 5, 19] 且 k = 2，则输出将为 36，因为子序列为 [10, 2, 5, 19]。
为了解决这个问题，我们将遵循以下步骤：
ret := -inf
定义一个数组 dp 并将给定数组复制到其中
定义一个双端队列 dq
将 v[0] 插入 dq 的开头
n := v 的大小
ret := v[0]
对于初始化 i := 1，当 i < n 时，更新（将 i 增加 1），执行：
如果 i > k 且 dq 的第一个元素与 dp[i - k - 1] 相同，则
从 dq 中删除第一个元素
dp[i] := dp[i] 和（如果 dq 为空，则 dp[i] + 0，否则 dp 的第一个元素 + dq[i]）中的最大值
当（dq 不为空且 dq 的最后一个元素 < dp[i]）时，执行：
从 dq 中删除最后一个元素
将 dp[i] 插入 dq 的末尾
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
更新于： 2020-06-09
114 次查看
广告