设 $f[i]$ 为以 $a[i]$ 为结尾LIS的长度，$\forall j<i\wedge a[j]<a[i]$，我们就有这个转移：

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

$f[i]$ 初始为 $1$，因为最坏情况（即 $\forall j<i$ 都有 $a[j]\ge a[i]$）下以 $a[i]$ 为结尾的LIS长度就为 $1$。

但最后的答案并不一定为 $a[n]$，如这组数据：

$$2\ 3\ 4\ 5\ 6\ 2$$

很明显答案为 $5$，但 $f[n]$ 为 $1$ 不是最优答案。正确答案应为 $f[1]\sim f[n]$ 的最大值。

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

需要注意不能在枚举 $j$ 之前就将 $f[i]$ 设为 $1$。