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)


相关推荐

  • Centos7更换阿里云yum源

    Centos7更换阿里云yum源

  • 有刷/无刷动力电调与马达知识

    有刷/无刷动力电调与马达知识模型车需要行驶,就跟真车一样,需要一套动力单元,也有分电动和油动,至于混合动力这个估计就不需要奢望了,对于车模这么小的空间来说是不现实的,而且模型车也不需要考虑燃油经济性的问题。本文则重点介绍电动模型的动力单元。电动模型的动力,主要是指2个元件:第一就是带动车架行驶的电机(Motor),也称马达/摩打等。第二就是控制电机转速的调速器(SpeedController),很久之前早期的调速器…

  • javascript页面刷新的几种方法[通俗易懂]

    javascript页面刷新的几种方法[通俗易懂]javascript页面刷新的几种方法javascriptrefreshpage几种页面刷新的方法window.location.reload(),window.history.go(0)和document.execCommand(”Refresh”),这三个方法是最快速的。其他的都有明显的浏览器滚动条的出现。Javascript刷新页面的几种方法: 1

  • quicktime player屏幕录制_电脑自带录屏怎么使用

    quicktime player屏幕录制_电脑自带录屏怎么使用Mac电脑用自带软件QuickTimePlayer进行录屏的教程,几步就可以学会,挺简单的。  1、首先,找到并打开QuickTimePlayer软件。可以鼠标右键这个图标,选择“选项”-“在程序坞中保留”,这样,软件就固定在了Dock栏,方便以后打开软件。  2、启动软件后,屏幕顶部左上角出现“QuickTimePlayer”栏目。  3、这时,我们点击屏幕左上角“QuickTimePlayer”栏目右边的“文件”选项,选择“新建屏幕录制”菜单项。  4、这时,屏…

  • supergo任我行纵行指南针TT硕点YY考勤打卡定位下载及安装教程

    supergo任我行纵行指南针TT硕点YY考勤打卡定位下载及安装教程**supergo指南针TT硕点YY定位下载及安装教程**supergo指南针TT硕点YY定位下载及安装教程(2021最新版更新)本文以supergo为例,演示说明下载过程1、首先登录supergo下载官网2、2.找到supergo下载的按钮。并点击下载,输入提示密码3.然后选择右上角三个点,选择在safari浏览器中打开。点击下载,安装。弹框请选择安装按钮4.点击设置-通用,描述文件和设备管理,找到证书名称,然后点击信任,即可…

  • WIFI 2.4G及5G信道一览表

    WIFI 2.4G及5G信道一览表目前主流的无线WIFI网络设备802.11a/b/g/n/ac:传统802.11•1997年发布•两个原始数据率:1Mbps和2Mbps•跳频展频(FHSS)或直接序列展布频谱(DSSS)•三个不重叠的信道中,工业、科学、医学(ISM)频段频率为2.4GHz•最初定义的载波侦听多点接入/避免冲撞(CSMA-CA)802.11a•1999年发布•…

发表回复

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

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