文章目录

• 最长上升子序列
• 最长上升子序列II

一、最长上升子序列IO链接

本题思路:本题是一关于dp问题中的一个类型是最长上升子序列问题，首先我们将状态表示出来：f[i]表示以a[i]结尾的最大的上升序列。状态计算（集合划分）：j∈(0,1,2,..,i-1),a[i]>a[j]，f[i] = max(f[i], f[j] + 1)。最后在找f[i]的最大值。

#pragma G++ optimize("Ofast,no-stack-protector");
#include<bits/stdc++.h>using namespace std;#define ios() ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define rep3(j,b,m) for(int j=b;j<m;j++)
#define rep4(j,b,m) for(int j=b;j<=m;j++)
typedef long long LL;inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;
}void print(int x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10^48);
}constexpr int N=1010;int n;
int a[N];
int f[N];int main()
{ios();n=read();rep2(i,1,n) a[i]=read();/*状态表示：f[i]表示以a[i]结尾的最大的上升序列。状态计算（集合划分）：j∈(0,1,2,..,i-1), a[i]>a[j]f[i] = max(f[i], f[j] + 1)。最后在找f[i]的最大值。*/int ans=0;rep2(i,1,n){f[i]=1;//最小的就是自己为1rep3(j,1,i)if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);ans=max(ans,f[i]);}print(ans);return 0;
}

N=1010#初始化dp数组为1
#表示以第i个字符结尾最长上升子序列长度
dp=[1]*Nn=int(input())
a=[int(x) for x in input().split()]for i in range(n):for j in range(i):if a[j]<a[i]:dp[i]=max(dp[i],dp[j]+1)print(max(dp))

二、最长上升子序列IIIO链接

本题思路:上面问题的优化写法，对于数据量很大时可以考虑二分优化，首先找到一个最大的小于等于当前数的数, 我们可以用 二分 来优化，先定义边界，l = 0, r = len, 其中len是q数组的长度
通过q[r + 1] = a[i]来将x覆盖a的值，即r + 1 > len时, 表示超出了二分边界，这时就要len ++更新q的长度。

#include <bits/stdc++.h>constexpr int N=100010;int n;
int a[N],q[N];int binary_search(int l,int r,int x)
{while(l<r){int mid=l+r+1>>1;if(q[mid]<x) l=mid;else r=mid-1;}return l;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n;for(int i=0;i<n;i++) std::cin>>a[i];int len=0;for(int i=0;i<n;i++){int l=0,r=len;int k=binary_search(l,r,a[i]);//找出第一个小于等于当前的数len=std::max(len,k+1);//此时k+1超出len，则需要更新lenq[k+1]=a[i];}std::cout<<len<<std::endl;return 0;
}

N=100010q=[0]*Nn=int(input())
a=[int(x) for x in input().split()]len=0
for i in range(n):l=0r=lenwhile l<r:mid=(l+r+1)//2if q[mid]<a[i]: l=midelse:r=mid-1len=max(len,r+1)q[r+1]=a[i]print(len)