最长上升子序列

Longest Increasing Subsequence

最长上升子序列:

有两种基本方法:两个时间复杂度分别为O(n^2)和O(nlogn)

对于给定数列a，元素个数为n，f[i]为以元素i结尾的最长子上升序列的最大长度。

最长上升子序列f满足对任意1<=j<i<=n(a[j]<a[i])，有f[j]<f[i]。

容易得出O(n^2)的DP状态转移方程:

f[i]=max{f[j]}+1;(1<=j<i且a[j]<a[i])

我们不妨把f的初值设为0，并在末尾添加一个元素inf，并将n++

这样经过两重循环，f[n]即为LIS长度

代码如下:

又称作CMI算法

时间复杂度为O(nlogn)

其操作如下:

开辟一个栈b，每次取栈顶元素s和读到的元素a做比较，如果a>s，则置为栈顶;如果a<s，则二分查找栈中的比a大的第1个数，并替换。最终栈的大小即为最长递增子序列为长度

考察b栈内每个元素的含义,b[i] 表示所有长度为i的上升子序列中最小的最后一个数.

·举例:原序列为3，4，5，2，4，2

栈为3，4，5，此时读到2，则用2替换3，得到栈中元素为2，4，5，再读4，用4替换5，得到2，4，4，再读2，得到最终栈为2，2，4,最终得到的解是:

长度为1的上升子序列中最小的最后一个数是2 (2)

长度为2的上升子序列中最小的最后一个数是2 (2,2)长度为3的上升子序列中最小的最后一个数是4 (3,4,4)

可知没有长度为4的上升子序列,最长递增子序列长度为3. (3,4,4)

CMI本质是LIS问题的另一种动态规划思路

注意:CMI只能求LIS的长度和最后一个数,不能求LIS的序列!

代码如下:

#include<iostream>

using namespace std;

int n;

int a[1001],b[1001];

int rear;

int solve(int t)

{ int l=1,r=rear;

while(l<=r)

{ int mid=(l+r)>>1;

if(b[mid]>=t)//若为非递减序列，则为b[mid]>t

r=mid-1;

else

l=mid+1;

}

if(l>rear)

rear=l;

return l;

}

int main()

{ int i,j;

scanf("%d",&n);

rear=0;

for(i=1;i<=n;i++)

{

scanf("%d",&a[i]);

b[solve(a[i])]=a[i];

}

printf("%d\n",rear);

system("pause");

return 0;

}