AcWing 895. 最长上升子序列

题目链接：

https://www.acwing.com/problem/content/897/

题解：

一维DP问题，非常经典

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;
int a[N],f[N];
int n;


int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    
    for(int i=1;i<=n;i++){
        f[i] = 1;
        for(int j=1;j<i;j++){
            if(a[i] > a[j]){
                f[i] = max(f[i],f[j]+1);
            }
        }
    }
    
    int res = -1;
    for(int i=1;i<=n;i++) res = max(res,f[i]);
    
    cout << res;
    return 0;
}