c++算法之最长递增子序列(LIS)

c++算法之最长递增子序列(LIS)题目:输入一个整数n,随后输入n个整数,求这个长度为n的序列中严格递增的子序列的最长长度。例:输入:6143265输出:3解题思路:动态规划。将输入的序列存入一个数组v中,另外再定义一个数组a,用以存储以当前数字v[i]结尾时,最长递增子序列的长度是多少。定义数组时,全部初始化为1,初始状态表示的是最坏的情况,以v[i]结尾的最长递增子序列就是v[i]它本身,长度为1。接着将v[i]逐一…

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

题目:
输入一个整数n,随后输入n个整数,求这个长度为n的序列中严格递增的子序列的最长长度。

例:
输入:

6
1 4 3 2 6 5

输出:
3

解题思路:
动态规划。将输入的序列存入一个数组v中,另外再定义一个数组a,用以存储以当前数字v[i]结尾时,最长递增子序列的长度是多少。

定义数组时,全部初始化为1,初始状态表示的是最坏的情况,以v[i]结尾的最长递增子序列就是v[i]它本身,长度为1。接着将v[i]逐一与前面的数字v[x]进行比较,x∈[0,i),若发现v[x]<v[i],说明v[i]可作为后继元素增加到以v[x]结尾的递增子序列中,则a[i]=v[x]+1,但是在将v[i]逐一与v[x]进行比较的过程中,我们需要找出最大的v[i],所以将每一次v[i]需要更新的值与它本身的值进行比较,取大的那一个就行了,保持在每一次v[i]与v[x]比较之后,v[i]的值都是最大的。最后,找出数组v中最大值就是结果。
再来看看样例,a[0]~a[5]的初始值都是1,
首先求以v[1]结尾的最长递增子序列长度。v[1]>v[0],说明4可作为1的后继成为递增序列,以1结尾的递增序列长度a[0]为1(默认值),则a[1]可以等于a[0]+1,同时a[1]本身也是1,a[0]+1>a[1],所以最终a[1]=a[0]+1=2;接着求v[2]
结尾的最长递增子序列长度,将v[2]与v[0]进行比较,v[2]>v[0]同时a[0]+1>a[2],所以a[2]=a[0]+1=2;将v[2]与v[1]进行比较,v[2]<v[1],则a[2]的值不变,最终a[2]=2;接着求v[3]结尾的最长递增子序列长度,v[3]>v[0]且a[0]+1>a[3],a[3]=a[0]+1=2;v[3]<v[1],a[3]值不变为2;v[3]<v[2],v[3]值不变为2,所以最终a[3]的值为2。后面的v[4]与v[5]依此类推。
代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
 int n;
 cin>>n;
 vector<int> v(n);
 vector<int> a(n,1);
 for(int i=0;i<n;i++)
  cin>>v[i];
 for(int i=1;i<n;i++)
  for(int j=0;j<i;j++)
   if(v[i]>v[j])
    a[i]=max(a[i],a[j]+1);
 sort(a.begin(),a.end());
 cout<<a[n-1];
 return 0;
}

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

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

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

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

(0)


相关推荐

  • 在MySQL中如何使用覆盖索引优化limit分页查询

    在MySQL中如何使用覆盖索引优化limit分页查询

  • 计算机网络bs/cs区别_bs嵌入cs

    计算机网络bs/cs区别_bs嵌入csCS什么是CS?CS(Client/Server)指客户端、服务器架构模式。客户端需要安装专用的客户端软件。CS的优点、特点1.交互性强2.存取模式安全3.网络通信量低4.响应速度快5.利于处理大量数据●能充分发挥客户端PC的处理能力,很多工作可以在客户端处理后再提交给服务器,所以CS客户端响应速度快。●操作界面漂亮、形式多样,可以充分满足客户自身的个性化要求。●C/S结构的管理信息系统…

    2022年10月17日
  • php 微信授权登录 40029错误[通俗易懂]

    php 微信授权登录 40029错误[通俗易懂]php微信授权登录40029错误授权登录是微信高级api,个人开发可以使用微信测试账号进行开发。在授权的过程可能出现40029错误码,解决的方法可以通过将code写在session里。publicfunctiongetUserDetail(){$appid=”xxxxxxxxxxxx”;$redirect_uri=urlencode(“

  • html5移动开发–js温馨提示

    html5移动开发–js温馨提示

  • manjaro 安装分区以及配置方案

    manjaro 安装分区以及配置方案制作启动盘windows下制作启动盘推荐在windows下使用Rufus工具来制作启动盘,做成启动盘后还能用来存储文件linux下制作启动盘使用dd命令,使用该命令做成启动盘后U盘就不能用来存储文件了,具体命令格式可以看wikihttps://wiki.manjaro.org/index.php?title=Burn_an_ISO_File#Using_t…

  • 笔记本卡顿不流畅是什么原因_笔记本卡顿不流畅是什么原因_笔记本电脑卡顿不流畅如何解决-win7之家…「建议收藏」

    笔记本卡顿不流畅是什么原因_笔记本卡顿不流畅是什么原因_笔记本电脑卡顿不流畅如何解决-win7之家…「建议收藏」有不少笔记本电脑用户在使用过程中,发现会经常会遇到卡顿不流畅的情况,很多用户不知道是什么原因引起的,其实原因有很多,可能是电脑本身配置不足,或者电脑占用率过高,或者内存不足等,接下来给大家带来笔记本电脑卡顿不流畅的详细解决方法吧。具体步骤如下:1、CPU不足电脑卡顿很多时候都是因为CPU占用过高,实质还是CPU太小引起的,我们可以将多余的进程或者软件关闭,或者更换性能好的CPU来解决这个问题,电脑…

发表回复

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

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