最长上升子序列nlogn算法

全栈程序员站长

发布于 2022-09-05 10:14:30

2560

发布于 2022-09-05 10:14:30

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

最长上升子序列nlogn算法

题目描述：

给定一个整型数组，求这个数组的最长严格递增子序列的长度。譬如序列1 2 2 4 3 的最长严格递增子序列为1，2，4或1，2，3.他们的长度为3。

输入：

输入可能包含多个测试案例。对于每个测试案例，输入的第一行为一个整数n(1<=n<=100000)：代表将要输入的序列长度输入的第二行包括n个整数，代表这个数组中的数字。整数均在int范围内。

输出：

对于每个测试案例，输出其最长严格递增子序列长度。

样例输入：

样例输出：

2
1

AC代码：

#include<stdio.h>
#include<string.h>

#define MAX 100000

int main(void)
{
	int n,top;
	int num[MAX],Stack[MAX];
	int low,mid,high;
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		top=0;
		memset(Stack,0,sizeof(Stack));
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		Stack[top]=-0xFFFFFF;
		for(i=0;i<n;i++)
		{
			if(num[i]>Stack[top])
				Stack[++top]=num[i];
			else
			{
				low=1;
				high=top;
				while(low<=high)
				{
					mid=(low+high)/2;
					if(num[i]>Stack[mid])
						low=mid+1;
					else
						high=mid-1;
				}
				Stack[low]=num[i];
			}
		}
		printf("%d\n",top);
	}

	return 0;
}

原理：栈中的数字越小，子串越长的可能性越大。。。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/137386.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年6月2，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法