求数组的最长递加子序列《编程之美》

求数组的最长递增子序列《编程之美》

#include<iostream>using namespace std;int main(){    extern int f(int [],int);int a[8]={1,-2,5,-3,-1,4,6,0};    int m=f(a,8);    cout<<"最长递增子序列的长度是"<<m<<endl;system("Pause");return 0;}int f(int arry[],int n){  //Lis[i]存储着以arry[i]为最后一个元素的序列（该序列是递增子序列）的长度int *Lis=new int[n];   int i=0;   for(;i<n;i++)   {     Lis[i]=1;   }   for(i=0;i<n;i++)   {     for(int j=0;j<i;j++) {  if(arry[i]>arry[j]&&Lis[i]<Lis[j]+1)//动态规划的思想，状态转移方程的程序实现步骤  Lis[i]=Lis[j]+1; }   }      int max=Lis[0];  for(int k=1;k<n;k++)  {   if(Lis[k]>max) max=Lis[k];  }  delete []Lis;  return max;}