【u023】最长上升子序列(sequence)
序列 最长 sequence 上升
2023-09-14 09:03:46 时间
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
非常经典的问题,拿来给大家练手了。 序列 { 1,2,...,n } 的一个子序列是指序列 { i1, i2, ……, ik },其中 1<=i1 < i2 < …… < ik<=n, 序列 { a1, a2, ……, an } 的一个子序列是指序列 { ai1, ai2, ……, aik },其中 { i1, i2, ……, ik } 是 { 1, 2, ……, n } 的一个子序列.同时,称 k 为此子序列的长度. 如果 { ai1, ai2, ……, aik } 满足 ai1 ≤ ai2 ≤ …… ≤ aik,则称之为上升子序列.如果不等号都是严格成立的,则称之为严格上升子序列.同理,如果前面不等关系全部取相反方向,则称之为下降子序列和严格下降子序列. 长度最长的上升子序列称为最长上升子序列.本问题对于给定的整数序列,请求出其最长上升子序列的长度.
【输入格式】
第一行给出一个数字N,N < = 5000,表示给定数列的长度。第二行有N个整数, 表示数列中的元素
【输出格式】
输出K的极大值,即最长上升子序列的长度
【数据规模】
Sample Input1
5 9 3 6 2 7
Sample Output1
3
【样例说明】
最长上升子序列为3,6,7
【题解】
程序1,用f[i]表示以i作为最后一个元素的最长上升子序列长度,f[i] = max(f[i],f[j]+1),其中 a[i] >= a[j]; j ∈(1,i-1);
程序2,用f[i]表示长度为i的最长上升子序列的最后一个元素的最小值,在扫描输入的数组a时,如果a[i] > f[maxl],那么maxl++,f[maxl] = a[i],否则 从maxl-1 到 1扫描一下,
找到最大的j使得a[j] <= a[i] ,然后 f[j+1] = a[i];即更新长度为j+1的最长上升子序列的最后一个数的最小值。最后输出maxl就好。
程序2可以用二分查找来优化做到nlogn,但是二分查找写起来很麻烦、
【程序1】
#include <cstdio> int n,a[5002],f[5002],ans = 0; void input_data() { scanf("%d",&n); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); } int ma_x( int a,int b) { if (a > b) return a; else return b; } void get_ans() { for (int i = 1;i <= n;i++) { f[i] = 1;//f[i] == 1表示 从这个数字开始新的一个序列 长度为1 for (int j = 1;j <= i-1;j++) //或者从之前的序列中更新,让这个数字作为最后一个数 { if (a[i] >= a[j]) //前提是这个数字要比前面的数字大 且长度加上1之后会比这个数字作为其他序列的最后一个数字来的更好(长度更长) f[i] = ma_x(f[i],f[j] + 1); } if (f[i] > ans) // 如果比最优解更优 则更新 ans = f[i]; } } void output_ans() { printf("%d\n",ans); } int main() { input_data(); get_ans(); output_ans(); return 0; }
【程序2】
#include <cstdio> int n,a[5002],f[5002],ans = 0,maxl = 0; void input_data() { scanf("%d",&n); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); for (int i = 1;i <= n;i++) f[i] = 0; f[0] = -200000000;//这个f[0]的边界 可以方便后面的求解 } void get_ans() { for (int i = 1;i <= n;i++) { if (a[i] >= f[maxl]) //如果比最长长度的序列的最后一个数字大 就可以更新长度了,这样是最优的 { maxl++; f[maxl] = a[i]; } //没有办法更新最大长度 就在前面的数字中找,更新一下最后一个数字的最小值 else for (int j = maxl-1; j >=0; j--) //从大到小更新这样保证是最大的j if (f[j] <= a[i]) { f[j+1] = a[i]; break; } } } void output_ans() { printf("%d\n",maxl); } int main() { //freopen("F:\\rush.txt","r",stdin); input_data(); get_ans(); output_ans(); return 0; }
相关文章
- 小明の魔法计划——最长上升子序列[通俗易懂]
- 最长公共子序列与最长公共子串
- acwing-最长上升公共子序列(动态规划)[通俗易懂]
- 128. 最长连续序列
- 最长回文子串 python_最长回文子序列
- R语言广义相加模型 (GAMs)分析预测CO2时间序列数据|附代码数据
- 2022-12-22:给定一个数字n,代表数组的长度, 给定一个数字m,代表数组每个位置都可以在1~m之间选择数字, 所有长度为n的数组中,最长递增子序列长度为
- C++ 最长公共子序列 Sub Sequence
- 【动态规划】最长非降子序列 01背包 插入加号
- BAT面试算法进阶- 最长的斐波那契子序列的长度(暴力法)
- R语言神经网络模型预测多元时间序列数据可视化
- Oracle序列号重置指南(oracle序列重置)
- Oracle序列值:轻松获取唯一标识码(oracle序列值)
- MySQL中创建序列的实战操作(mysql创建序列)
- MySQL序列:解锁更高数据处理能力(mysql的序列)
- 值Oracle取序列值的简单操作(oracle取序列)
- C语言实现最长递增子序列问题的解决方法