陈顺凡-6分.txt

这是很不错的计算机算法

#include <iostream>
#include <fstream>
using namespace std;
int LIS2Length(int n,int *a)
{//改进算法，时间复杂度可达nlogn,b为存储"子序列的"最大递增子序列的最末元素
 int len,i,p,r,m,*b;//p,r,m分别为二分查找的上界，下界和中点
 len=1;//Len为当前最大递增子序列长度，初始化为1
 b=new int[n+1];
 b[0]=-100000;//把B[0]设为最小，假设任何输入都大于-100000
 b[1]=a[0];//初始时，最大递增子序列长度为1的最末元素为a1
 for(i=1;i<n;i++)
 {
  p=0;r=len;
  while (p<=r)//二分查找最末元素小于ai+1的长度最大的最大递增子序列
  {
   m=(p+r)/2;
   if (b[m]<=a[i]) p=m+1;
   else r=m-1;
   }
  b[p]=a[i];//将长度为p的最大递增子序列的当前最末元素置为ai,p相当于f(i)
  if (p>len) len++;//更新当前最大递增子序列长度,也可以从b[p]中知道这个序列的最大值
  cout<<"i="<<i<<"  "<<a[i]<<"  "<<"p="<<p<<"  "<<b[p]<<endl;
 }
 
 return len;
}
void main()
{
 int i,ML,n,*a;
 ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
        exit(1);
	}
 ofstream out("output.txt");
 in>>n;
 a=new int[n];
 for(i=0;i<n;i++)
	 in>>a[i]; 
 ML=LIS2Length(n,a);
 out<<ML<<endl;
 in.close;
 out.close;
}