1、B站视频链接：E03 线性DP 最长上升子序列_哔哩哔哩_bilibili

#include <bits/stdc++.h>
using namespace std;
int n=9;
int a[101]={0,5,7,1,9,4,6,2,8,3};
int f[101];
//f[i]表示以a[i]为结尾的
//最长上升子序列的长度 
int main(){
	int i,j,ans=1;
	for(int i=1;i<=n;i++){
		f[i]=1;//初始化f[i]即自身长度为一的序列 
	}
	//动态更新f[i] //i,j双指针扫描 
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>a[j]){
				f[i]=max(f[j]+1,f[i]);//长度加一或者不变 
			}
		}
		ans=max(ans,f[i]);
	} 
	//输出最长长度
	printf("%d\n",ans); 
	return 0;
}

2、B站视频链接：E04 线性DP 最长上升子序列 二分优化_哔哩哔哩_bilibili

注意：b数组存储的并不是最长上升子序列2567，b数组仅能得出最长上升子序列的长度

#include <bits/stdc++.h>
using namespace std;
int n=9;
int a[101]={0,2,5,9,4,6,7,1,7,2};
int b[101];//记录上升子序列
int len;//上升子序列的长度
int find(int x){//二分查找第一个大于等于x的位置 
	int l=1,r=len,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(x>b[mid])l=mid+1;
		else r=mid-1;
	}
	return l; 
}
int main(){
	int i,j;
	len=1;
	b[1]=a[1];
	//动态更新b数组
	for(int i=2;i<=n;i++){
		if(a[i]>b[len]){//大于则添加 
		    b[++len]=a[i];	
		}else{//小于等于则替换,越小b数组变长的概率越大 
			j=find(a[i]);//二分查找 
			b[j]=a[i];
		}
	}
	printf("%d\n",len);
	return 0;
}