前置知识：
\(LIS\) :
即最长上升子序列 ( \(Longest\) \(Increasing\) \(Subsequence\) )
这是一个简单的动规板子题。
给出一个由 \(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;
}