最长不下降子序列 C++

来源:百度知道 编辑:UC知道 时间:2024/05/11 17:53:55
C++最长不下降子序列的代码 速度
代码

#include"stdio.h"
void main()
{
int i,j,tempMax;
int nCase=1;
int a[32767];
int totalMax[32767];
int temp;
while(scanf("%d",&temp))
{
if(temp==-1)break;
a[1]=temp;
totalMax[1]=1;
for(i=1;;)
{
scanf("%d",&temp);
if(temp==-1)break;
else
{
a[++i]=temp;
tempMax=0; //找到i之前 的totalMax[j]最大且a[j]>a[i]的j值
for(j=1;j<i;j++)
if(a[i]<a[j]&&tempMax<totalMax[j])tempMax=totalMax[j];
totalMax[i]=tempMax+1; //i取的是上面得到的值,加上本身(因为有a[j]>a[i]),所以+1
}
}
temp=0;
for(j=1;j<=i;j++)
if(totalMax[j]>temp)temp=totalMax[j];
printf("Test #%d:\n"