小工具知识网

当前位置: 首页 > 行业知识 > 最长上升子序列c++

行业知识

最长上升子序列c++

2026-11-18 20:22:57 来源:互联网转载
题目

���入样例:

73 1 2 1 8 5 6

输出样例:

4

 

思路

题目求最大长度,考虑使用DP来做。我们从状态表示和状态计算两方面进行分析。

假设用a数组来存序列,f数组来存以f[i]结尾的最长上升子序列。

1. 状态表示:

这一步我们思考如何定义集合。

集合f(i)定义:以f[i]结尾的所有序列。

集合属性(即f[i]存的值):最大长度。

因为题目要求最长上升子序列,通过这样定义集合,我们可以枚举所有序列,并可以求出所有以f[i]结尾的最长上升子序列,那我们就可以f[i]中选出一个最大的作为答案了。

 

2. 状态计算:

这一步我们思考如何把每个f[i]求出来。

要计算以f[i]结尾的最长上升子序列,那么我们可以利用在a[i]这个数之前算过的最长上升子序列f[j],如果a[j] 小于 a[i],说明a[i] 是可以放到a[j]后面 成为一条长度为f[j] + 1的上升子序列的。如果a[i]能放到多条f[j]后面,那么以a[i]结尾的最长上升子序列为f[i] = max(f[i], f[j] + 1)。

代码
#includeusing namespace std;const int N = 1010;int a[N], f[N];int main(){  int n;  cin >> n;    for (int i = 1; i > a[i];    int res = 1;  for (int i = 1; i = 0; j --)    if (a[i] > a[j])    f[i] = max(f[i], f[j] + 1);        res = max(res, f[i]);  }    cout 

上一篇:携程服务器托管地点揭秘

下一篇:服务器支持esweb怎么设置?