最长上升子序列问题

最长上升子序列

给定一长度为n的数列，请在不改变原数列顺序的前提下，从中随机的取出一定数量的整数，并使这些整数构成单调上升序列。输出这类单调上升序列的最大长度。

数据范围：1n

n平方的处理方式

维护这样一个数组，dp[i]=x，表示以a[i]为结尾的最长上升子序列的长度。当我们已知上升序列的最后一个元素a[i]时，若想知道以它结尾的最长上升序列长度，只需遍历1~i-1这一范围，寻找末尾元素比a[i]小且长度最长的上升序列，和a[i]组成新的上升序列即可。

dp[i]=max(dp[i],dp[j]+1),1

此时复杂度为O(n2)

#include

#include

usingnamespacestd;

intn,ans=1;

inta[100005]={};

intdp[100005]={};

intmain(){

cin>>n;

for(inti=1;i

cin>>a[i];

dp[i]=1;

}

for(inti=1;i

for(intj=1;j

if(a[j]

}

ans=max(ans,dp[i]);

}

cout

return;

}

nlogn的处理方式

从n平方的算法开始进行分析，复杂度高的原因在于需要寻找尾元素比a[i]小且长度最长的上升序列。而之前维护的dp数组，存储长度的无序的，要寻找一个满足条件的最值，只能一个个进行枚举。若想对寻找进行优化，我们就能想到二分查找，而二分的前提条件是答案单调有序。

那么如何使长度有序？我们换个思路维护新数组dp[i]=x,表示长度为i的最长上升子序列的末尾元素是x。我们将原先的下标与存储的内容交换下位置，此时长度即下标就有序了。并且，数组的权值也一定可以是单调上升的。对于同样的长度，结尾元素值越小结果是越优。

此时，我们只需枚举a数组，若a[i]>=最长上升序列的末尾元素，则将a[i]加入最长上升序列。若不满足，则将a[i]更新dp数组中第一个末尾值比a[i]大的数，或者说末尾元素值大于等于a[i]的序列中值最小的那个。显而易见，可以使用二分方式进行处理。时间复杂度为O(nlogn)

dp[1]=a[1];

for(inti=2;i

if(a[i]>=dp[len]){

len++;

dp[len]=a[i];

}else{

// 寻找在1~len范围内>=a[i]的最小值

// 由于单调增 可以二分查找

intl=1,r=len,mid;

while(l

mid=(l+r)/2;

if(dp[mid]>=a[i]){

r=mid-1;

}else{

l=mid+1;

}

}

dp[l]=a[i];

}

}

代码实现

#include

usingnamespacestd;

intn,len=1,ans=1;

inta[100005]={};

intdp[100005]={};

intmain(){

cin>>n;

for(inti=1;i

cin>>a[i];

}

dp[1]=a[1];

for(inti=2;i

if(a[i]>=dp[len]){

len++;

dp[len]=a[i];

}else{

// 寻找在1~len范围内>=a[i]的最小值

// 由于单调增 可以二分查找

intl=1,r=len,ans=-1,mid;

while(l

mid=(l+r)/2;

if(dp[mid]>=a[i]){

r=mid-1;

}else{

l=mid+1;

}

}

dp[l]=a[i];

}

}

cout

return;

}