闫式dp分析法

/*

    分析  ： 
        1) 集合划分 1 3 2 5 4
        2)  转移
             2-1）如果 i > j 那么证明以i为结尾的序列可以继承j的上升序列 所以 f[i] = f[j] + 1 
             2-2) 如果 i < j 那么代表他不能继承他的序列，但是在1 ~ j 之间可能有序列可以被i继承 

        3) 结果 if a[i] > a[j]  
                    f[i] = max(f[i] , f[j] + 1);      


*/
#include <iostream>
#include <algorithm>
#include <cstring>

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];

    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 res = 0;
    for (int i = 1 ; i <= n ; i ++ ) res = max(res , f[i]);
    cout << res << endl;

    return 0;
}