这道题完全懵了,网上的答案也不怎么看的懂,幸亏得到OI大佬的指点
大家可以先看一下这里,还有这篇详细的介绍
题目的提示还是很重要的
#include <stdio.h>
#define MAX 65535
int bsearch(int*,int);
int main(void)
{
int num[9]={2,1,3,0,4,1,5,2,7};
int result[9]={0};
int log[9];
for(int i=0;i<9;i++)
log[i]=MAX;
int len=1;//subsequence length
for(int i=0;i<9;i++)
{
if(num[i]<log[0])
{
log[0]=num[i];
if(len<=1)
{
result[0]=num[i];
}
}
else
{
int j=bsearch(log,num[i]);
log[j+1]=num[i];
if(j+1>=len)
{
result[j+1]=result[j];
result[j+1]=num[i];
}
if(j+1>=len)
len++;
}
}
printf("%d",len);
for(int i=0;i<9;i++)
printf("%d",result[i]);
return 0;
}
int bsearch(int* base,int data)
{
int left,mid,right;
left=0;right=9;
while(left<right)
{
mid=left+(right-left)/2;
if(base[mid]>=data)
right=mid;
else
left=mid+1;
}
if(base[left]<data&&base[left+1]>=data)
return left;
else
return left-1;
}