医疗微网站建设计划书,自己网上开店怎么做,网站数据流程,网站续费如何做分录文章目录题目解法DP暴搜思路代码实现贪心二分思路代码实现题目
给出一组数据 nums#xff0c;求出其最长下降子序列#xff08;子序列允许不连续#xff09;的长度。#xff08;类似于lc的最长递增子序列#xff09; 示例#xff1a; 输入#xff1a;
6 // 数组元素个…
文章目录题目解法DP暴搜思路代码实现贪心二分思路代码实现题目
给出一组数据 nums求出其最长下降子序列子序列允许不连续的长度。类似于lc的最长递增子序列 示例 输入
6 // 数组元素个数
3 4 3 5 2 1 // 数组输出
4 // 最长下降子序列为4321长度为4解法
DP暴搜
思路
DP数组 表示 nums数组 对应下标的元素作为末尾时最长下降子序列的长度因此将 DP数组中的元素 全部初始化为 1最起码这个下降子序列里有当前元素。
从 nums 的第二个元素开始记为 i向前搜索所有大于它的元素记为 j找到后 dp[i] max(dp[i], dp[j] 1) 。举个例子会更直观
nums 3 4 3 5 2 1
dp 1 1 2 1 3 4⬆形成下降子序列4,3 在 i4, nums[i]2 时这个状态转移方程显得尤为重要
从 j0 开始遍历第一个大于 2 的元素是 j1, nums[j]4 dp[i]dp[j]12意味着可以形成下降子序列4,2长度为 dp[i]2第二个大于 2 的元素是 j2, nums[j]3 dp[i]dp[j]13意味着可以形成下降子序列4,3,2第三个大于 2 的元素是 j3, nums[j]5 dp[i]dp[i]3意味着形成 5,2 不如形成 4,3,2 更长所以仍保持原来的下降子序列。
值得注意的是最长下降子序列的长度是 DP数组 中最大的元素而非尾元素举个例子
nums 3 4 3 5 2 3
dp 1 1 2 1 3 2因此在构建 DP数组 的同时要记得保存最大元素哦~
代码实现
int main() {int n, res 1;cin n;vectorint v(n), dp(n, 1);for (int i 0; i n; i) {cin v[i];}for (int i 1; i n; i) {for (int j 0; j i; j) {if (v[j] v[i]) dp[i] max(dp[j] 1, dp[i]);}res max(dp[i], res);}cout res endl;
}贪心二分
思路
dp数组 用来暂存一个 下降子序列注意这里的序列并非真正的最长下降子序列至于原因下文解释。由于题目要求的是最长下降子序列的长度并不用返回序列的具体排列因此dp数组的长度就是本题的答案。
该方法思路分三步请客、斩首、收下当狗。
请客遍历 数据数组 中每个元素和 dp数组 的尾元素比较。收下当狗如果比较结果是当前遍历到的元素小于 dp数组 尾元素则当前元素直接加入 dp数组成为新的尾元素。斩首斩 dp数组 中旧元素的首当前遍历到的元素作为新元素自然要先收下当狗具体做法是 通过二分法找到 dp数组 中所有小于当前元素中最大的那个用当前元素替换掉它。举个例子比如dp数组元素是 9531。当前遍历到的元素是 6那么dp数组会变成9631。 为什么说 dp数组 暂存的下降子序列只是和真正的最长下降子序列长度相等两者内容并不一样 原因就在于第3点——斩首斩首的目的是 在不改变子序列长度的基础上扩大下降子序列的最小值用具体例子来说明
假如给出的数据是 343521。那么 dp数组 的变化会是
dp数组内容当前遍历到的元素最长下降子序列 333444 或 34,334,3535435322432532114321
代码实现
int main() {int n;cin n;vectorint v(n), dp;for (int i 0; i n; i) {cin v[i];}dp.push_back(v[0]);for (int i 1; i n; i) {if (v[i] dp.back()) dp.push_back(v[i]);else {int l 0, r dp.size()-1;while (l r) {int m l (r - l) / 2;if (v[i] dp[m])l m 1;else r m;}dp[l] v[i];}for (int j : dp) {cout j ;}cout endl;}cout dp.size() endl;
}
