POJ2533 Longest Ordered Subsequence 最長升序子序列

最長升序子序列一般有兩種解法，一種是經典的動态規劃方法，複雜度為O(n^2)，另外一種方法則借助棧和二分查找，複雜度為O(nlgn)。

動态規劃

設d[i]表示以a[i]結尾的最長升序子序列的長度，則可以得到狀态轉移方程為d[i]=max{1,max{d[j]}+1}，其中j=0,1,2,...i-1并且a[j]<a[i]。用一句話概括思路就是每次計算d[i]時，就要掃描數組a中前i-1個元素，如果遇到a[j]>a[i]則跳過a[j]繼續掃描j...i-1的元素，否則如果a[j]<a[i]則用以a[j]為結尾的子序列長度+1就是以a[j]為倒數第二個元素，a[i]為倒數第一個元素的最長子序列長度。之是以要求a[j]<a[i]很明顯是因為要求的是升序子序列，之是以max{d[j]}是因為要求的是最長的子序列，是以要找到前i-1個元素中子序列長度最大的然後+1。

棧+二分查找

http://www.slyar.com/blog/longest-ordered-subsequence.html

這種方法很直覺，比較好了解，用一句話說就是順次掃描數組，如果a[i]大于棧頂的元素則入棧，否則在棧中找到第一個大于a[i]的元素t并用a[i]替換t。如

1 7 3 5 9 4 8

棧為1 7 的時候，輸入3，則要替換7變為1 3，然後輸入5大于棧頂的3，直接入棧變為1 3 5=>1 3 5 9=>1 3 4 9=>1 3 4 8。最後的top就是最長升序子序列的長度。

AC_CODE：

#include <stdio.h>

#define N 1001

//動态規劃
int a[N];
int dp[N];

/************************************************************************/
/* 0MS 156K*/
/************************************************************************/
int lis(int n)
{
	int i,j,max;
	for(i=0;i<n;i++)
		dp[i]=1;
	for(i=1;i<n;i++)
	{
		max=-1;
		//j從0開始
		for(j=0;j<i;j++)
		{
			if(a[j]>=a[i]) continue;
			max=(dp[j]>max)?dp[j]:max;
			dp[i]=(max+1>1)?max+1:1;
		}
	}
	max=-1;
	for(i=0;i<n;i++)
		max=(dp[i]>max)?dp[i]:max;
	return max;
}

/************************************************************************/
/* 16MS 156K*/
/************************************************************************/
int a[N];
int stack[N];

int lis(int n)
{
	int top,i,l,m,r;
	top=-1;
	stack[++top]=a[0];
	for(i=1;i<n;i++)
	{
		if(a[i]>stack[top])
			stack[++top]=a[i];
		else
		{
			l=0;r=top;
			while(l<=r)
			{
				m=(l+r)>>1;
				if(stack[m]<a[i])
					l=m+1;
				else
					r=m-1;
			}
			stack[l]=a[i];
		}
	}
	return top+1;
}
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	printf("%d\n",lis(n));
	return 0;
}