草庐IT

最长上升子序列（c++图文详解）

kano_s 2023-10-15 原文

这题思路是这样，假设这个序列长度为n，存在数组a中，maxlen[i]表示以第i个数为终点的最长上升子序列的长度，它被初始化为1，因为一开始单个字符的最长上升子序列都是1（它自己），我们先用一个循环i遍历这个序列，i从2（序列的第2个字符）开始一直加1加到n，表示求以第i个数为终点的最长上升子序列的长度，然后同时在这个循环下再来一个循环j，j从1开始加1一直加到i-1为止，表示以第j个数为终点的最长上升子序列。只要出现a[i]>a[j]的情况，maxlen[i]=max(maxlen[i],maxlen[j]+1),首先看maxlen[j]+1,因为a[i]>a[j]了，说明以第j个数为终点的最长上升子序列后面又多了一位比这个最长上升子序列大的，也就是a[i]，这个序列变成以a[i]为终点的了，所以长度要加1，注意j的范围是（1,i-1）,所以以第i个数为终点的最长上升子序列的长度至少是maxlen[j]+1,再跟maxlen[i]比较，因为maxlen[i]通过更新是有可能比maxlen[j]+1大的。

我们用图来表示这个解法，以题目例子的序列来说：

初始时单个字符的最长上升子序列是它本身，为1：

第1次i从2（对应数字7）开始，所以j从1到i-1也就是1 （对应数字1），7>1,我们发现a[i]>a[j]了，所以maxlen[i]=max(maxlen[i],maxlen[j]+1)，maxlen[2]=max(1,1+1),maxlen[2]=2,所以在7下面的1数是1下面的1数再加一笔：

 第2次i从3（对应数字3）开始，所以j从1到i-1也就是1,2（对应数字1,7）,发现3比1大，所以3下面的1数是1下面的1数又加一笔，也就是比谁大，就把谁下面的1的数量拿（覆盖原来的）过来再加1，比7小所以不加：

 接着i到4（对应数字5）了，比j的数字1和3都大，但是比较后3下面的1数最多，所以以它的加1，覆盖到5上，5下面就对应3了，接着i到9以此类推，最后的图是这样：

有几个1就代表了以这个数为终点的最长上升子序列的长度是多少，最后直接求最大输出就行了。 

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int a[maxn];
int maxlen[maxn]={0};
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)//存入序列，并初始化maxlen[i]
	{
		cin>>a[i];
		maxlen[i]=1;
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(a[i]>a[j])
				maxlen[i]=max(maxlen[i],maxlen[j]+1);
		}
	}
	int maxone=-1;
	for(int i=1;i<=n;i++)//找出maxlen[i]中值最大的
	{
		maxone=maxone>maxlen[i]?maxone:maxlen[i];
	}
	cout<<maxone<<endl;
	return 0;
}

 

 

c++详解xffxff0cxff0算法动态规划

有关最长上升子序列（c++图文详解）的更多相关文章

  1. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  2. ruby - 在 Ruby 中比较序列 - 2

    假设我必须(小型到中型)阵列:tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]如何确定tokens是否以相同的顺序包含template的所有条目？(请注意，在上面的示例中，应忽略第一个“ccc”，从而由于最后一个“ccc”而导致匹配。) 最佳答案 这适用于您的示例数据。tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]po

  3. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  4. ruby-on-rails - 在 Elastic Beanstalk 上升级 Ruby - 2

    如何在ELB上设置和更新ruby​​版本？我已经在我们的qa和暂存环境中使用ruby2.2.2大约8个月了。我刚刚在星期一设置我们的生产环境，它不会部署，因为它说ruby​​设置为2.2.3而我的gemfile说2.2.2。我更新并重新部署，一切似乎都很好。我回到了qa/staging环境，但无法将其更新到ruby​​2.2.3。一直说ruby版本是2.2.2，Gemfile是2.2.3我升级了(通过elbui):运行Ruby2.2(PassengerStandalone)的64位AmazonLinux2015.03v1.3.1到运行Ruby2.2(PassengerStandalon

  5. 机器学习——时间序列ARIMA模型(四)：自相关函数ACF和偏自相关函数PACF用于判断ARIMA模型中p、q参数取值 - 2

    文章目录1、自相关函数ACF2、偏自相关函数PACF3、ARIMA(p,d,q)的阶数判断4、代码实现1、引入所需依赖2、数据读取与处理3、一阶差分与绘图4、ACF5、PACF1、自相关函数ACF自相关函数反映了同一序列在不同时序的取值之间的相关性。公式：ACF(k)=ρk=Cov(yt,yt−k)Var(yt)ACF(k)=\rho_{k}=\frac{Cov(y_{t},y_{t-k})}{Var(y_{t})}ACF(k)=ρk​=Var(yt​)Cov(yt​,yt−k​)​其中分子用于求协方差矩阵，分母用于计算样本方差。求出的ACF值为[-1,1]。但对于一个平稳的AR模型，求出其滞

  6. 物联网MQTT协议详解 - 2

    一、什么是MQTT协议MessageQueuingTelemetryTransport：消息队列遥测传输协议。是一种基于客户端-服务端的发布/订阅模式。与HTTP一样，基于TCP/IP协议之上的通讯协议，提供有序、无损、双向连接，由IBM（蓝色巨人）发布。原理：（1）MQTT协议身份和消息格式有三种身份：发布者（Publish）、代理（Broker）（服务器）、订阅者（Subscribe）。其中，消息的发布者和订阅者都是客户端，消息代理是服务器，消息发布者可以同时是订阅者。MQTT传输的消息分为：主题（Topic）和负载（payload）两部分Topic，可以理解为消息的类型，订阅者订阅（Su

  7. Tcl脚本入门笔记详解（一） - 2

    TCL脚本语言简介•TCL（ToolCommandLanguage）是一种解释执行的脚本语言（ScriptingLanguage）,它提供了通用的编程能力：支持变量、过程和控制结构；同时TCL还拥有一个功能强大的固有的核心命令集。TCL经常被用于快速原型开发，脚本编程，GUI和测试等方面。•实际上包含了两个部分：一个语言和一个库。首先，Tcl是一种简单的脚本语言，主要使用于发布命令给一些互交程序如文本编辑器、调试器和shell。由于TCL的解释器是用C\C++语言的过程库实现的，因此在某种意义上我们又可以把TCL看作C库，这个库中有丰富的用于扩展TCL命令的C\C++过程和函数，所以，Tcl是

  8. ruby-on-rails - Rails 编辑序列化的 JSON 数据 - 2

    我有一个存储JSON数据的列。当它处于编辑状态时，我不知道如何显示它。serialize:value,JSON=f.fields_for:valuedo|ff|.form-group=ff.label:short=ff.text_field:short,class:'form-control'.form-group=ff.label:long=ff.text_field:long,class:'form-control' 最佳答案 代替=f.fields_for:valuedo|ff|请使用以下代码:=f.fields_for:va

  9. ruby-on-rails - 序列化时无法将空数组保存到数据库 - 2

    在RubyonRails中，如果数组为空，则具有序列化数组字段的模型将不会在.save()上更新，而它之前有数据。我正在使用:ruby2.2.1rails4.2.1sqlite31.3.10我创建了一个字段设置为文本的新模型:railsgmodel用户名:stringexample:text在我添加的User.rb文件中:serialize:example,Array我实例化了User类的一个新实例:test=User.new然后我保存用户以确保它正确保存:test.save()(0.1ms)begintransactionSQL(0.4ms)INSERTINTO"users"("cr

  10. ruby - 加载使用 YAML 序列化的对象时调用初始化 - 2

    是否可以在使用YAML.load_file时强制Ruby调用初始化方法？我想调用该方法以便为我不序列化的实例变量提供值。我知道我可以将代码分解成一个单独的方法并在调用YAML.load_file之后调用该方法，但我想知道是否有更优雅的方法来处理这个问题。 最佳答案 我认为你做不到。由于您要添加的代码确实特定于要反序列化的类，因此您应该考虑在类中添加该功能。例如，让Foo成为您要反序列化的类，您可以添加一个类方法，例如:classFoodefself.from_yaml(yaml)foo=YAML::load(yaml)#editth

随机推荐