动态规划-子序列问题——300.最长递增子序列

1.题目解析

题目来源:300.最长递增子序列——力扣

测试用例

2.算法原理

1.状态表示

首先创建一个与数组大小相同的dp表,此时dp[i]表示的是:以第i个位置为结尾的所有子序列中最长递增子序列的长度

2.状态转移方程

此时第i个位置一定是最长递增子序列的最大值,因此需要向前判断即nums[j] < nums[i],当找到小于的值就可以放入递增子序列,此时求dp[j]+1与dp[i]的最大值即可

3.初始化

由于递增子序列的最小值一定是1,也就是1个数也可以构成递增子序列,那么就可以将dp表的所有元素均初始化为1,这样就不用单独判断单个数字的递增子序列长度

4.填表顺序

从左到右,每个位置单独判断

5.返回值

返回整个dp表的最大值,因为最长递增子序列可能出现在任何一个位置 

3.实战代码

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n,1);int ret = 1;for(int i = 1;i < n;i++){for(int j = 0;j < i;j++){if(nums[j] < nums[i]){dp[i] = max(dp[j] + 1,dp[i]);}}ret = max(ret,dp[i]);}return ret;}
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/455839.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot中yml文件多环境配置

yml文件多环境配置步骤如下&#xff1a; 1、在application.yml同级目录下创建配置文件&#xff0c;格式为&#xff1a; application-环境名.yml&#xff0c;示例如下&#xff1a; 2、通过主配置文件application.yml中的spring.profiles.activexxx指定具体的环境。 建议配置&a…

Chrome谷歌浏览器加载ActiveX控件之JT2Go控件

背景 JT2Go是一款西门子公司出品的三维图形轻量化预览解决工具&#xff0c;包含精确3D测量、基本3D剖面、PMI显示和改进的选项过滤器等强大的功能。JT2Go控件是一个标准的ActiveX控件&#xff0c;曾经主要在IE浏览器使用&#xff0c;由于微软禁用IE浏览器&#xff0c;导致JT2Go…

股票与基金资料收集

声明&#xff1a;本内容是网上资料的收集与整理而成&#xff0c;不定时更新。仅供参考&#xff0c;不构成任何投资建议。 目录&#xff1a; 一、股票 1、黄金交叉和死亡交叉 2、技术指标 3、T、TR、THR含义 二、基金 平准基金 一、股票 1、黄金交叉和死亡交叉 “黄金交…

CSS 网格布局

网格布局是一个二维布局系统&#xff0c;允许开发者以行和列的形式创建灵活的网络&#xff0c;并将内容放置在网络的单元格中。有些元素可能只占据网络的一个单元&#xff0c;另一些元素则可能占据多行或多列。 网格的大小既可以精确定义&#xff0c;也可以根据自身内容自动计…

【算法篇】动态规划类(4)——子序列(笔记)

目录 一、Leetcode 题目 1. 最长递增子序列 2. 最长连续递增序列 3. 最长重复子数组 4. 最长公共子序列 5. 不相交的线 6. 最大子序和 7. 判断子序列 8. 不同的子序列 9. 两个字符串的删除操作 10. 编辑距离 11. 回文子串 12. 最长回文子序列 二、动态规划总结 …

ctfshow-web入门-web31

<?php ​ /* # -*- coding: utf-8 -*- # Author: h1xa # Date: 2020-09-04 00:12:34 # Last Modified by: h1xa # Last Modified time: 2020-09-04 00:49:10 # email: h1xactfer.com # link: https://ctfer.com ​ */ ​ error_reporting(0); if(isset($_GET[c])){$c …

Java语言-接口(下)

目录 1. 接口使用实例 1.1 给对象数组排序 1.2 Clonable接口和深拷贝 Cloneable 浅拷贝 深拷贝 1.3 抽象类和接口的区别 2. Object类 2.1 Object类的介绍 2.2 toString() 2.3 equals() 2.4 hashcode() 1. 接口使用实例 1.1 给对象数组排序 现有一个学生类&#…

关于java继承(深入解析父类属性的抽取与构造函数的作用)

目录 前言基础继承作用 理论分析父类属性的抽取构造函数调用父类构造函数会不会创建一个父类的对象&#xff1f;生命周期角度谁的属性用谁的构造函数初始化 示例解析代码代码调试展示构造函数初始化成员变量 总结 前言 在Java中&#xff0c;继承是一项至关重要的特性&#xff0…

详解23种设计模式——第二部分:结构型模式

目录 3 结构型模式 3.1 代理模式 3.2 适配器模式 3.2.1 默认适配器模式 3.2.2 对象适配器模式 3.2.3 类适配器模式 3.2.4 适配器模式总结 3.3 桥梁模式 3.4 装饰模式 3.4 门面模式 3.5 组合模式 3.6 享元模式 3.7 结构型模式总结 接上一篇&#xff1a;详解23种设计…

openrtp 音视频时间戳问题

解决音视频发送的rtp问题 openrtp增加了音频aac的发送&#xff0c;地址 OpenRTP Gitee开源地址 同时使用两个rtp &#xff0c;来发送音频和视频 使用以下音频rtp&#xff0c;是可以发送和接收的&#xff0c;音频端口在视频端口上2 v0 o- 0 0 IN IP4 127.0.0.1 sMy Stream cI…

Windows通过netsh控制安全中心防火墙和网络保护策略

Windows通过netsh控制安全中心防火墙和网络保护策略 1. 工具简介 【1】. Windows安全中心 【2】. netsh工具 netsh(Network Shell) 是一个Windows系统本身提供的功能强大的网络配置命令行工具。 2. 开启/关闭防火墙策略 在设置端口&#xff08;禁用/启用&#xff09;前&am…

使用 CDN 后 Apache 的日志记录客户真实 IP

经常搭建网站服务器的都知道&#xff0c;在给站点使用了 CDN 后 Web 应用的日志记录里就会只记录 CDN 节点 IP 了&#xff0c;这就没法看到真实客户请求 IP&#xff0c;对于日志分析、运维日常维护来说就有点儿麻烦了&#xff0c;今天明月结合在五洛云服务器上搭建的Apache环境…

多ip访问多网站

多IP访问多网站 1.预配操作 [rootlocalhost ~]# mount /dev/sr0 /mnt mount: /mnt: WARNING: source write-protected, mounted read-only. [rootlocalhost ~]# systemctl stop firewalld ----------关闭防火墙 [rootlocalhost ~]# setenforce 0 -------关闭selinux2.安装n…

【论文阅读】ESRGAN

学习资料 论文题目:增强型超分辨率生成对抗网络(ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks)论文地址:[1809.00219] ESRGAN:增强型超分辨率生成对抗网络代码:xinntao / ESRGAN:ECCV18 研讨会 - 增强的 SRGAN。Champion PIRM Challenge 关于感知…

【机器学习】VQ-VAE(Vector Quantized Variational Autoencoder)

VQ-VAE&#xff08;Vector Quantized Variational Autoencoder&#xff09;是一种生成模型&#xff0c;它结合了变分自编码器&#xff08;Variational Autoencoder, VAE&#xff09;和向量量化&#xff08;Vector Quantization&#xff09;技术。VQ-VAE的主要目的在于通过离散潜…

【动态规划】子序列问题(上)

1. 最长递增子序列 300. 最长递增子序列 和子数组不同的是&#xff0c;子数组要求是连续的&#xff0c;子序列只要下标是递增的就可以&#xff0c;这里严格递增的意思是不能有相等的元素&#xff0c;必须一直递增 状态表示&#xff1a;以 i 位置为结尾的所有的子序列中最长递…

Android GPU Inspector分析帧数据快速入门

使用 谷歌官方工具Android GPU Inspector (AGI) 可以对Android 应用进行深入和全面的系统性能分析和帧性能分析 。AGI 是一个非常强大的分析工具&#xff0c;尤其是在需要诊断 GPU 性能问题和优化应用时&#xff0c;可以帮助你精准找到性能瓶颈。本文介绍如何使用该工具对帧数据…

梳理一下spring中,与message相关的知识点

本次梳理的相关知识点包括jms&#xff0c;amqp(rabbitmq)&#xff0c;sping-messaging&#xff0c;spring-integration&#xff0c;springcloud-stream&#xff0c;这些都是与消息message相关的内容&#xff0c;它们有什么区别与联系呢&#xff1f; 相关的要点与相互关系都整理…

物联网消息队列Emqx日志配置及日志追踪以及Centos7上的rc.local开机不执行、git提交的小问题

一、物联网消息队列Emqx日志配置及日志追踪 EMQX支持将日志输出到控制台或者日志文件&#xff0c;或者同时使用两者。使用 Docker 部署 EMQX&#xff0c;默认只能通过 docker logs 命令查看 EMQX 日志。EMQX 的默认日志级别为 warning&#xff0c;默认在单日志文件超过10MB(log…

word压缩大小怎么弄?快来试试这几种压缩word方法!

word压缩大小怎么弄&#xff1f;在处理Word文档时&#xff0c;如果遇到体积过大的情况&#xff0c;无疑会带来一系列麻烦&#xff0c;大型Word文档不仅占据大量存储空间&#xff0c;而且在传输过程中会耗费更多时间&#xff0c;想象一下&#xff0c;当你急需将一份重要的文档发…