最长不减子序列.txt

来自「一些典型DP题的代码」· 文本 代码 · 共 65 行

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

//最长不减子序列

#define NMAX 200
#define MIN -30000
int shuru[NMAX];
int ans[NMAX];

int find(int key,int len)
{
	int low,high,mid,max=ans[0];
	low=1;high=len;mid=(low+high)/2;
	while(low<=high)
	{
		if(key<ans[mid]) high=mid-1;//注意是<
		else
		{
			max=mid;
			low=mid+1;
		}
		mid=(low+high)/2;
	}
	if(max==ans[0]) return 0;
   	else return max;	
}

int solve(int num)
{
	int i,len=1,j;
	ans[0]=MIN;
	ans[1]=shuru[1];
	for(i=2;i<=num;i++)
	{
		if(shuru[i]>=ans[len])	ans[++len]=shuru[i];//注意是>=
		else
		{
			j=find(shuru[i],len);
			ans[j+1]=shuru[i];
		}
	}
	return len;
}


void print(int len)
{
	int i;
	printf("len=%d\n",len);
	for(i=1;i<=len;i++) printf("%d ",ans[i]);
	printf("\n");
}
int main()
{
	int i,num,len;
	scanf("%d",&num);
	for(i=1;i<=num;i++) scanf("%d",&shuru[i]);
	len=solve(num);
	print(len);
	return 0;
}