题目描述： 最长上升子序列

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

输入格式

第一行包含整数N。

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

输出格式

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

数据范围

1≤N≤1000
−1e9≤数列中的数≤1e9

输入样例

7
3 1 2 1 8 5 6

输出样例

4

基本思考框架

C++ 代码

这个写法时间复杂度是：n(状态数量)*n{状态计算) = O(N^2)

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int a[N];
int n;

int main()
{
    cin>>n;
    for(int i = 1 ; i <= n ;i++)
        cin>>a[i];

    int res = 0;
    for(int i = 1 ;  i <= n ;i ++ )
    {   int tmp = 0;
        for(int j = 1 ; j <= i ; j ++)
            if(a[j]<a[i])
                tmp = max(tmp,f[j]);
        f[i] = tmp + 1;
        res = max(res,f[i]);
    }

    cout<<res<<endl;
    return 0;
}

Post modified: 2019-10-24