最长上升子序列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)


相关推荐

  • cuda安装错误_n卡图形驱动安装失败

    cuda安装错误_n卡图形驱动安装失败win7安装cuda9时出现图形驱动程序安装失败,解决办法是右键计算机>管理>服务和应用程序>服务>找到“WindowsInstaller”,右键选择“启动”参考自http

  • jquery实现轮播图_用jquery实现图片轮播图代码

    jquery实现轮播图_用jquery实现图片轮播图代码HTML代码:&lt;divclass="content_right"&gt;&lt;divclass="ad"&gt;&lt;ulclass="slider"&gt;&lt;li&gt;&lt;imgsrc=&quot

  • 旋转机械振动的基本特性分析图_旋转机械振动监测及故障诊断

    旋转机械振动的基本特性分析图_旋转机械振动监测及故障诊断旋转机械的主要功能是由旋转部件来完成的,转子是其最主要的部件。旋转机械发生故障的主要特征是机器伴有异常的振动和噪声,其振动信号从幅域、频域和时域反映了机器的故障信息。因此,了解旋转机械在故障状态下的振动机理,对于监测机器的运行状态和提高诊断故障的准确率都非常重要。一、转子振动的基本特性旋转机械的主要部件是转子,其结构型式虽然多种多样,但对一些简单的旋转机械来说,为分析和计算方便,一般都将转

  • Oracle 恢复数据到某个时间节点

    Oracle 恢复数据到某个时间节点–注意:恢复的时间点与当前时间节点表结构需要一致,truncate的数据无法恢复–1.创建临时表保存该时间节点表的数据createtabletemp_table–临时表asselect*fromT_PM_ParamItem–原表asoftimestampto_timestamp(‘2018-01-1211:11:11’,’yyyy-mm-ddhh24…

  • Hibernate5.0配置C3P0连接池步骤详解

    Hibernate5.0配置C3P0连接池步骤详解Hibernate5.0拥有自己的数据库连接池,但是无论性能和功能都不如C3P0(本人新手,查取资料得知),由于之前苦搜资源都不得愿,所以写下此篇文章以供像我一样苦于搜索的新手,以供参考。   Hibernate5.0整合C3P0实现连接池的步骤如下:   首先第一步   1).到https://sourceforge.net/projects/hibernate/到该网站

发表回复

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

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