LIS

• 状态：$f_i$ 表示以第 $i$ 个元素结尾的最长上升子序列的长度。

• 转移：$ f_i = \begin{matrix} max\{1,f_j +1\} & \text{ if } j<i,a_j<a_i \end{matrix} $

• 目标：$max\{f_i\}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;

int main(int argc, char* argv[]) {
    int n; cin >> n;
    vector<int> a(n + 1), f(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;
    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);
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}