LIS（最长上升子序列）
这是O（n^2）的算法：
#include<stdio.h>
int main()
{
int n,i,k,max,lis[1001],num[1001];
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",&num[i]);
lis[i]=1;
}
for(i=1;i<n;i++)
for(k=0;k<i;k++)
if(num[k]<=num[i]&&lis[i]<lis[k]+1) //当前数比之前数大&&当前记录值≤之前记录值，这样，把当前记录值加一
lis[i]++;
max=1;
for(i=0;i<n;i++)
if(max<lis[i])
max=lis[i];
printf("%d\n",max);
}
return 0;
}
O（n*log2n）的算法：用到二分
例如：
lis[]中原先存入：1 5 7，再输入新数据num=3，则更新lis[1]=5为lis[1]=3，即求比num大的最小的lis[]中的数，进行替换。
//求最长上升子序列
#include<stdio.h>
int lis[40001];
int binarysearch(int left,int right,int number)
{
int mid;
while(left<=right)
{
mid=left+(right-left)/2;
if(lis[mid]<number) left=mid+1;
else right=mid-1;
}
return right;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n,p,i,tot,num,meet;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
scanf("%d%d",&p,&num);
lis[0]=num;
tot=1;
for(i=1;i<p;i++)
{
scanf("%d",&num);
if(num>lis[tot-1])
lis[tot++]=num; //如果num比lis[]末尾数大，则lis[]下标自增，存入num
else if(num<lis[tot-1]) //如果num比lis[]末尾数小，则用二分法找到比num大的最小的数的下标，然后进行替换
{
meet=binarysearch(0,tot-1,num);
lis[meet+1]=num;
}
}
printf("%d\n",tot);
}
}
return 0;
}
我还看到另一种用二分做的，还没想明白，继续研究
//最长不下降子序列
#include<stdio.h>
int lis[1002];
int binarysearch(int left, int right, int number)
{
int mid;
while(left<=right)
{
mid=left+(right-left)/2;
if(lis[mid]<=number) left=mid+1; //
else right=mid-1;
}
return left;
}
int main()
{
int n,num,rightest,meet;
while(scanf("%d", &n)!=EOF)
{
lis[0]=-1;
rightest=0;
while(n--)
{
scanf("%d",&num);
meet=binarysearch(0,rightest,num); //找到填入数据的位置
lis[meet]=num;
if(meet>rightest) //若返回的位置比原来的大，那么记录最右边位置的值加一
rightest++;
}
if (!rightest)
rightest=1;
printf("%d\n",rightest);
}
}
优质内容筛选与推荐>>
1、9.10 模拟赛
2、Android开始之Checkboxs
3、201621123030《Java程序设计》第1周学习总结
4、Swift 使用 LLDB 调试命令
5、laravel 返回值