1 int lis(int array[]){ 2     int n=sizeof(array); 3     //定义lisMax存放当前的最长递增序列 4     int nMax=1; 5     //list[i]中放着从array[0]到array[i]找到的最长递增序列的长度,初始化都为1 6     int* list=new int[n]; 7     for(int i=0;i<n;i++) 8         list[i]=1; 9     //长度为i的递增子序列最大元素的最小值为maxV[i]10     int* maxV=new int[n+1];11     maxV[0]=minArray(array)-1;12     maxV[1]=array[0];13     //更新list[i]和maxV[i]14     for(int i=2;i<n;i++){15         //遍历历史最长递增序列信息16         int j;17         for(j=list[i-1];j>=0;j++){18             if(array[i]>maxV[j]){19                 list[i]=j+1;20                 break;21             }22         }23         //如果当前list[i]>nMax,更新lisMax和maxV24         if(list[i]>nMax){25             nMax=list[i];26             maxV[nMax]=array[i];27         }28         else if(maxV[j]<array[i] && array[i]<maxV[j+1])29                 maxV[j+1]=array[i];30         else continue;31     }32     return nMax;33 }