前置知识：

\(LIS\) :

即最长上升子序列 ( \(Longest\) \(Increasing\) \(Subsequence\) )

Luogu B3637 最长上升子序列

这是一个简单的动规板子题。
给出一个由 \(n(n\le 5000)\) 个不超过 \(10^6\) 的正整数 (\(x_1,x_2, \cdots ,x_n\)) 组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

设计状态 \(dp[i]\) 代表以第 \(i\) 个数字结尾的最长上升子序列。
并且有两层循环，第一层枚举 \(i\) 即结尾数字。
第二层枚举 \(j\) 从 \(1 \to i - 1\) 枚举结尾数字前的数字，并进行状态转移。
状态转移的条件：当 \(x_i > x_j\) 时，说明 \(dp[i]\) 可以继承 \(dp[j]\)
则有：

for(int i = 1;i <= n;i++){
    for(int j = i - 1;j >= 1;j--){
        if(a[i] > a[j]){
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

然后再从 \(dp[1],dp[2],\cdots,dp[n]\) 中选出最大值即可。
则有解：

#include<bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1000005;
int a[MAXN];
int dp[MAXN];
int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i++){
        scanf("%d", &a[i]);
        dp[i] = 1;
    }
    for(int i = 1;i <= n;i++){
        for(int j = i - 1;j >= 1;j--){
            if(a[i] > a[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    for(int i = 1;i <= n;i++){
        dp[i] = max(dp[i], dp[i - 1]);
    }
    printf("%d", dp[n]);
    return 0;
}