[动态规划] 最长递增子序列 (Longest Increasing Subsequence)

时间:2022-09-28 19:26:03

1.复杂度为O(n^2)

const int maxn=100020;
const int inf=0x3f3f3f3f;
int dp[maxn];//以a[i]为结尾的最长自增子序列长度
int a[maxn];
int n;

int LIS(int a[],int n)//最长上升子序列
{
int m;
dp[0]=1;
for(int i=1;i<n;i++)
{
m=0;
for(int j=1;j<i;j++)
{
if(dp[j]>m&&a[j]<a[i])
m=dp[j];
}
dp[i]=m+1;
}
return dp[n-1];
}

int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
cout<<LIS(a,n)<<endl;
}
return 0;
}

2.1 复杂度0(nlogn)

int a[maxn];
int b[maxn];
int n;

int bin_search(int aim,int low,int high)
{
while(low<=high)
{
int mid=(low+high)/2;
if(aim>b[mid])
low=mid+1;
else
high=mid-1;
}
return low;
}

int LIS(int a[],int n)
{
int len=0,pos;
for(int i=1;i<=n;i++)
{
if(a[i]>b[len]||len==0)
{
len++;
b[len]=a[i];
}
else
{
pos=bin_search(a[i],0,len);
b[pos]=a[i];
}
}
return len;
}

int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
cout<<LIS(a,n)<<endl;
}
return 0;
}



2.2 复杂度为0(nlogn),使用了库函数二分搜索 lower_bound()

lower_bound函数从已排好序的序列a中利用二分搜索找出指向ai>=k的ai的最小的指针。类似的函数含有upper_bound,这一函数求出的是指向ai>k的ai的最小的指针。有了它们,比如长度为n的有序数组a中的k的个数,可以这样求出
upper_bound(a,a+n,k) - lower_bound(a,a+n,k);

模板:

const int maxn=100020;
const int inf=0x3f3f3f3f;
int dp[maxn];
int a[maxn];
int n;

int LIS(int a[],int n)
{
//fill(dp,dp+n,0x7fffffff);
memset(dp,inf,sizeof(dp));
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
*lower_bound(dp,dp+n,a[i])=a[i];
}
int len=lower_bound(dp,dp+n,inf)-dp;
return len;
}

int main()
{
while(scanf("%d",&n)!=EOF)
{
cout<<LIS(a,n)<<endl;
}
return 0;
}