最长上升子序列_小明非常喜欢数列,于是他提出了一个关于数列的问题。他拿到一个长度为n的数列,之

---

一、最长上升子序列

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

二、使用步骤

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int n,res=-999999;
const int N=1010;
int a[N],f[N];
int main()
{
    cin >>n;
    for(int i=0;i<n;i++)
    cin >>a[i];
    for(int i=0;i<n;i++)
    {
        f[i]=1;//只有一个的时候
        for(int j=0;j<i;j++)
        {
            if(a[i]>a[j])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    for(int i=0;i<n;i++)
    res=max(f[i],res);
    cout <<res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

dp问题 最长上升子序列模板题
借用