最长上升子序列nlogn算法

最长上升子序列nlogn算法最长上升子序列nlogn算法题目描述:给定一个整型数组,求这个数组的最长严格递增子序列的长度。譬如序列12243的最长严格递增子序列为1,2,4或1,2,3.他们的长度为3。输入:输入可能包含多个测试案例。对于每个测试案例,输入的第一行为一个整数n(1输入的第二行包括n个整数,代表这个数组中的数字。整数均在int范围内。

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

最长上升子序列nlogn算法

题目描述:

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

输入:

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

输出:

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

样例输入:

4
4 2 1 3
5
1 1 1 1 1
样例输出:

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;
}


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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/137386.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号