Lisアルゴリズム

最も長男のシーケンスをより効率的に求めるアルゴリズムです.
はっきり言って、このアルゴリズムは配列を維持することで、最初はこの配列は何もありませんでした.
例を挙げると、我々が与えた配列はa[]={1 7 3 5 9 4 8}であり、その後、a[i]>b配列の最後の数であればlen+,b[len]=a[i]のルールに従うb配列(メンテナンス配列)を定義する.そうでなければ、既存の長さのb配列の中でa[i]より大きい最初の数を見つけて、a[i]で置き換えます.最後のb配列の長さは最長上昇サブシーケンスである.
具体的な手順は次のとおりです.
初めて私たちは1をb配列にあげましたb={1}
そして7対1の大きいb={1,7}
7は最初の3より大きい数で、3で7をb={1,3}に置き換えます.
5は3より大きいb={1 3 5}
9は5より大きいb={1 3 5 9}
5は最初の4より大きい数で、5 b={1 3 4 9}を4で置き換えます.
9は8より大きい最初の数で9 b={1 3 4 8}を8で置き換える
最長上昇シーケンスの長さは4です
code:

#if 1 //  
#include
using namespace std;
int binary(int val,int a[],int l,int r)
{
	int m;
	int id;
	while(l<=r)
	{
		m=l+(r-l)/2;
		if(a[m]>val)
		{
			id=m;
			r=m-1;	
		}
		else
			l=m+1;
		
	}
	return id;
}

int main()
{
	int a[1000],l,r,len=0;
	int b[1000];           //     
	int n;
	cin>>n; 
	for(int i=0; i>a[i];
	} 
	
	b[0]=a[0];
	len=1;
	for(int i=1; ib[len-1])
		{
			len++;
			b[len-1]=a[i];
		}
		else if(a[i]
using namespace std;

int main()
{
	int a[1000],l,r,len=0;
	int b[1000];           //     
	int n;
	cin>>n; 
	for(int i=0; i>a[i];
	} 
	
	b[0]=a[0];
	len=1;
	for(int i=1; ib[len-1])
		{
			len++;
			b[len-1]=a[i];
		}
		else
		{
			*lower_bound(b,b+len,a[i])=a[i]; 
		  
		}	
		for(int i=0; i