思路 ：

$f[i]$表示已$i$结尾の最长子序列

首先循环$n$遍，每一遍循环$i - 1$遍，寻找比$a[i]$小的数$j$，找到后已$j$作为结尾，

再加上1，就是加上本来的$i$，再选取$f[i] , f[j] + 1$中最大的作为$f[i]$。

则状态转移方程就是

$f[i] = max ( f[i] , f[j] + 1 ) $

(动态规划) $O(n^2)$

#include <bits/stdc++.h>

using namespace std ;

const int N = 1001 ;

int n ;
int a[N] ;
int f[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[j] < a[i] ) {

                f[i] = max ( f[i] , f[j] + 1 ) ;

            }

        }

    }

    int ans = -1 ;

    for ( int i = 1 ; i <= n ; i ++ ) ans = max ( ans , f[i] ) ;

    cout << ans ;

    return 0 ;

}