陈星娥-6分.txt

这是很不错的计算机算法

#include < iostream.h > 
#include < fstream.h >
#include < stdio.h > 

ofstream myoutf("output.txt"); //输出数据到文件,
void LISlength(int m,int * x,int * y);


void main()
{
int size; //定义序列的长度
int i; //循环变量
int * listx ; //序列x
int * listy; //分别记录以listx[i]为最末元素时，最长递增序列长度

ifstream myinf("input.txt",ios::nocreate); //读取文件
if (myinf.fail())
{
cerr << "读入文件时，出错！";
return; //如果没有输入文件，则返回错误
}
myinf >> size ; //序列个数
listx = new int[size];
for (i = 0;i < size; i++) 
 {
  myinf >> listx[i];
  cout << listx[i] << " ";
 }
 cout << endl;


listy = new int[size+1];
for (i = 0;i < size+1; i++) 
listy[i] = 0;//保存最长递增子序列长度的数组初始化


LISlength(size,listx,listy);



delete[] listx; 
delete[] listy;
myinf.close(); //关闭输入文件
myoutf.close(); //关闭输出文件
}



void LISlength(int n,int * a,int * b)
{
 int i , j; 

 b[0] = 1; 
 b[n] = 1; 

 for (i = 1; i < n; i++) //从1开始循环
  {
   b[i] = 1; //如果没有这样的序列存在，则最大递增子序列为1

   for (j = 0; j < i; j++) //从0开始循环，j < i
    {
      if ((a[i] >= a[j]) && (b[i] <= b[j]+1))
        {
          b[i] = b[j] + 1; 
        }
     }

      if (b[n] < b[i]) b[n] = b[i]; //判断最大的点，然后放到最后一个节点存储

   }
myoutf << b[n] << endl; //输出结果到文件
}