学步园

求最长上升子序列，用动态规划的方法，转移方程为：

D[i]=max{1,D[j]+1} j=1,2,...,i-1并且 A[j]<A[i]

#include<string>
#include<iostream>
using namespace std;

/*LIS
Slyar:属于简单的经典的DP，求最长上升子序列(LIS)。先研究了O(n^2)的思路。

  令A[i]表示输入第i个元素，D[i]表示从A[1]到A[i]中以A[i]结尾的最长子序列长度。对于任意的0 <  j <= i-1，如果A(j) < A(i)，则A(i)可以接在A(j)后面形成一个以A(i)结尾的新的最长上升子序列。对于所有的 0 <  j <= i-1，我们需要找出其中的最大值。
  
	DP状态转移方程:
	
	D[i] = max{1, D[j] + 1} (j = 1, 2, 3, ..., i-1 且 A[j] < A[i])
	  
	解释一下这个方程，i， j在范围内:
		
	 如果 A[j] < A[i] ，则D[i] = D[j] + 1
		  
	如果 A[j] >= A[i] ，则D[i] = 1
参考：http://www.slyar.com/blog/poj-2533-cpp.html

*/
//动态规划方法：方法1 时间复杂度O(n^2)
int LIS_1(int *A,int n){
	int *D;
	int i,j;
	int max=0;
	D=new int[n];
	for(i=0;i<n;i++){
		D[i]=1;
		for(j=0;j<i;j++){
			if(A[j]<A[i] && D[i]<D[j]+1)
				D[i]=D[j]+1;
		}
		if(max<D[i])
			max=D[i];
	}
	delete []D;
	cout<<"max="<<max<<endl;
	return max;
}

================类似贪心=================================================//方法2：时间复杂度 O(nlogn)
/*
这个算法的具体操作如下(by RyanWang):

 开一个栈（数组实现，其实就是个数组），每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的不小于temp的第1个数，
 并用temp替换它。 最长序列长度即为栈的大小top。	
举例：原序列为1，5，8，3，6，7
	  
栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。
见：http://www.slyar.com/blog/longest-ordered-subsequence.html#comments
 */
int LIS_2(int *A,int n){
	int *stack=new int[n];
	int i,top;
	int low,high,mid;
	stack[0]=A[0];
	top=0;
	for(i=1;i<n;i++){
		if(A[i]>stack[top])
			stack[++top]=A[i];
		else{
			low=0;
			high=top;
			while(low<=high){// 找到大于等于A[i]的第一个数，然后替换
				mid=(low+high)/2;
				if(A[i]==stack[mid]){
					low=mid;
					break;
				}
				else if(A[i]>stack[mid])
					low=mid+1;
				else
					high=mid-1;
			}
			stack[low]=A[i];
		}
	}
	for(i=0;i<=top;i++)
		cout<<stack[i]<<" ";
	cout<<endl;
	delete []stack;
	return (top+1);
}
int main(){
	int n;
	int *A;
	freopen("D:/test.txt","r",stdin);
	cin>>n;
	cout<<"n="<<n<<endl;
	int i;
	A=new int[n];
	for(i=0;i<n;i++){
		cin>>A[i];
	}
	cout<<LIS_1(A,n)<<endl;
	cout<<LIS_2(A,n)<<endl;
	delete []A;
	fclose(stdin);
	return 0;
}