lis最长上升子序列

因为是最长上升的，可以用一个数组储存上升的序列，如果后一个数字比数组的最大数字还大，就加到末尾去，如果不大于，那么就可以把这个数组中比他大的数字替换掉，因为如果数字更小，后面上升序列更长的可能性更大，这样也不会改变之前最大的数字；最小同理

#include<iostream>

#include<cstdio>

#include<algorithm>

#define sf scanf

#define pf printf

#define rep(i,a,b) for(int i=a;i<b;i++)

#define per(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

int a[100005];

int low[100005];

int h[100005];

int find(int le,int x)

{

	int l=1,r=le,mid;

	while(r>l)

	{

		mid=(l+r)/2;

		if(x>=h[mid])

		r=mid;

		else

		l=mid+1;

	}

	return l;

}

int main()

{

	int n,ans=1;

	sf("%d",&n);

	rep(i,1,n+1)

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

//	low[1]=a[1];//上升的

//	rep(i,2,n+1)

//	{

//		if(low[ans]<a[i])

//		low[++ans]=a[i];

//		else

//		{

//			int j=lower_bound(low+1,low+ans+1,a[i])-low;

//			low[j]=a[i];

//		}

//	}

	int ans1=1;//下降的

	h[1]=a[1];

	rep(i,2,n+1)

	{

		if(h[ans1]>a[i])

		h[++ans1]=a[i];

		else

		{

			int j=find(ans1,a[i]);

			h[j]=a[i];

		}

	}

	pf("%d\n",ans1);

	return 0;

}

巴特西

lis最长上升子序列

最新文章

热门文章