文章目录
- 最长上升子序列
- 最长上升子序列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]的最大值。文章来源:https://www.uudwc.com/A/20jzN/
#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;//最小的就是自己为1
rep3(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]*N
n=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的长度。文章来源地址https://www.uudwc.com/A/20jzN/
#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,则需要更新len
q[k+1]=a[i];
}
std::cout<<len<<std::endl;
return 0;
}
N=100010
q=[0]*N
n=int(input())
a=[int(x) for x in input().split()]
len=0
for i in range(n):
l=0
r=len
while l<r:
mid=(l+r+1)//2
if q[mid]<a[i]:
l=mid
else:
r=mid-1
len=max(len,r+1)
q[r+1]=a[i]
print(len)