代码随想录算法训练营第五十二天 | 300. 最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组

1. 最长递增子序列 

300. 最长递增子序列 - 力扣(LeetCode)

dp[i] 取决于 i 之前所有的dp

class Solution {public int lengthOfLIS(int[] nums) {// dp[i] 第 0 - i 位的递增子序列长度int length = nums.length;int[] dp =new int[length];Arrays.fill(dp, 1);int max = 1;for(int i = 1; i < length; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j])dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(dp[i], max);}return max;}
}

2. 最长连续递增序列

674. 最长连续递增序列 - 力扣(LeetCode)

dp[i] 取决于 i-1 的dp

class Solution {public int findLengthOfLCIS(int[] nums) {int length = nums.length;int[] dp = new int[length];Arrays.fill(dp, 1);int max = 1;for(int i = 1; i < length; i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1] + 1;}max = Math.max(max, dp[i]);}return max;}
}

3. 最长重复子数组

718. 最长重复子数组 - 力扣(LeetCode)

遍历两个数组,当前元素(及之前)的公共子数组 取决于 当前位置是否相等 和 前一位

注意,两个数组 中 有元素是第一个 要初始化为 1

class Solution {public int findLength(int[] nums1, int[] nums2) {//dp[i][j] nums1[i] nums2[j] 前(包含)的最长公共子数组 * 当前位置必须相等int l1 = nums1.length;int l2 = nums2.length;int[][] dp = new int[l1][l2];int max= 0;for(int i = 0; i < l1; i++){for(int j = 0; j < l2; j++){if(nums1[i] == nums2[j]){ // * 当前位置必须相等if( i == 0 || j == 0){dp[i][j] = 1;}elsedp[i][j] = dp[i-1][j-1] + 1;max = Math.max(max, dp[i][j]);}}}return max;}
}
nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

dp[2][2] = 0 不 = 1 因为 nums1[2] != nums2[2]

 

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

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

相关文章

基于SSM的微博系统网站的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用Vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

如何用ChatGPT学或教英文?5个使用ChatGPT的应用场景!

原文&#xff1a;百度安全验证 AI工具ChatGPT的出现大幅改变许多领域的运作方式&#xff0c;就连「学英文」也不例外&#xff01;我发现ChatGPT应用在英语的学习与教学上非常有意思。 究竟ChatGPT如何改变英文学习者(学生)与教学者(老师)呢&#xff1f; 有5个应用场景我感到…

2023-09-28 monetdb-databae的概念和作用-分析

摘要: 每个数据库对于db,schema以及user,role都有一套自己的设计, 不同数据库间对于相同名字的东西例如database和schema可以说南辕北辙, 例如mysql中schema其实是database的同义词. 本文分析monetdb的database的概念和作用 database的概念和作用: 和mysql的database完全不同…

Linux开发工具之文本编译器vim

目录 Linux编辑器-vim使用 1. vim的基本概念 ● 正常/普通/命令模式(Normal mode) ● 插入模式(Insert mode) ● 末行模式(last line mode) 2. vim的基本操作 ● [正常模式]切换至[插入模式] ● [插入模式]切换至[正常模式] ● [正常模式]切换至[末行模式] ● 退出vi…

步力宝科技爆款产品定位,开创智能物联网新商业

数据显示&#xff0c;中国处于 “亚健康”状态人口数量约占总人口的70%&#xff0c;亚健康是一种临界状态&#xff0c;指介于健康和疾病之间的状态。亚健康是一个动态演变的过程&#xff0c;既有向慢病发展的趋势&#xff0c;也能通过合理的干预使人体重返健康状态&#xff0c;…

网络运营和电子商务有什么区别

大家好&#xff0c;我是网络工程师成长日记实验室的郑老师&#xff0c;您现在正在查看的是网络工程师成长日记专栏&#xff0c;记录网络工程师日常生活的点点滴滴 一个同学他问我&#xff0c;他说学网络运营的话&#xff0c;它是不是电子商务里面的这个东西&#xff1f;像电子大…

南京大学【软件分析】08 Pointer Analysis

文章目录 1. Motivation2. Introduction to Pointer Analysis3. Key Factors of Pointer Analysis3.1 Heap Abstraction3.2 Context Sensitivity3.3 Flow sensitivity3.4 Analysis scope 4. Concerned Statements 1. Motivation 指针分析存在不精确的问题。对于下面的例子&…

快排三种递归及其优化,非递归和三路划分

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 目录 快排简介&#xff1a; 快排的三种递归实现&#xff1a; Hoare&#xff1a; 挖坑&#xff1a; 双指针&#xff1a; 小区间优化&#xff1a; 三数取中优化&#xff1a; 快排非递归实现&#xff1a; 快排的三路划…

Ubuntu配置深度学习环境(TensorFlow和pyTorch)

文章目录 一、CUDA安装1.1 安装显卡驱动1.2 CUDA安装1.3 安装cuDNN 二、Anaconda安装三、安装TensorFlow和pyTorch3.1 安装pyTorch3.2 安装TensorFlow2 四、安装pyCharm4.1 pyCharm的安装4.2 关联anaconda的Python解释器 五、VScode配置anaconda的Python虚拟环境 前言&#xff…

一维数组和二维数组的使用(char类型)

目录 导读1. 字符数组1.1 字符数组的创建1.2 字符数组的初始化1.3 不同初始化在内存中的不同1.3.1 strlen测试1.3.2 sizeof测试1.3.3 差异原因 1.4 字符数组的使用 2. 数组越界3. 数组作为函数参数博主有话说 导读 我们在前面讲到了 int 类型的数组的创建和使用&#xff1a; 一…

焕新古文化传承之路,AI为古彝文识别赋能

目录 1 古彝文与古典保护 2 古文识别的挑战 2.1 西文与汉文OCR 2.2 古彝文识别难点 3 合合信息&#xff1a;古彝文保护新思路 3.1 图像矫正 3.2 图像增强 3.3 语义理解 3.4 工程技巧 4 总结 1 古彝文与古典保护 彝文指的是云南、贵州、四川等地的彝族人使用的文字&am…

行为型设计模式——责任链模式

摘要 责任链模式(Chain of responsibility pattern): 通过责任链模式, 你可以为某个请求创建一个对象链. 每个对象依序检查此请求并对其进行处理或者将它传给链中的下一个对象。 一、责任链模式意图 职责链模式&#xff08;Chain Of Responsibility&#xff09; 是一种行为设…

MAC手动修复『已损坏』问题 终端运行命令报错处理

安装一些第三方软件会出现已损坏的报错提醒&#xff0c;需要用命令sudo xattr -rd com.apple.quarantine进行修复&#xff0c;但是终端提示命令错误&#xff0c;怎么版 错误有几种&#xff1a; No module named ‘pkg_resources’ 这是mac电脑上python2&#xff0c;python3并…

mfc140u.dll是什么文件?mfc140u放在哪个文件夹?详细修复教程

今天我想和大家分享一个非常常见的问题——mfc140u.dll丢失的困扰以及解决方法。 首先&#xff0c;让我们来了解一下什么是mfc140u.dll。这是一个非常重要的动态链接库文件&#xff0c;它是Microsoft Foundation Class Library的一个组件。许多软件和游戏都需要这个文件的支持才…

Appium 全新 2.0 全新跨平台生态,版本特性抢鲜体验!

关于Appium V2 Appium V2 beta版本在2021年发布&#xff0c;从2022年1月1号开始&#xff0c;Appium核心团队不会再维护Appium 1.x版本了&#xff0c;所有近期官方发布的平台驱动&#xff08;如Android平台的UIAutomator&#xff0c;IOS平台的XCUITest&#xff09;不再兼容Appi…

Qt多线程实现方式-moveToThread及其注意事项

Qt多线程实现方式-moveToThread及其注意事项 Chapter1 Qt多线程实现方式-moveToThread一、Qt下使用线程主要有两种方法。二、Qt下创建多线程也有两种方法。三、其它问题。 Chapter2 QT多线程接收串口数据1.前言2.功能作用3.软件测试效果4.基本步骤 Chapter3 利用Qt多线程机制实…

面试打底稿⑦ 项目一的第三部分

简历原文 抽查部分 完成路线规划模块选择路线功能&#xff0c;用neo4j这种存储图关系的非关系数据库&#xff0c;实现最短线路规划、最低成本线路规划 设计优化物流信息模块&#xff0c;合理选择数据库、缓存技术&#xff0c;实现数据精简、流量削峰、提高系统可 用性 模拟问答…

Scala第十五章节

Scala第十五章节 1. 递归 2. 案例一: 求阶乘 3. 案例二: 斐波那契数列 4. 案例三: 打印目录文件 scala总目录 文档资料下载

04、EL和JSTL核心技术

目录 1 EL表达式&#xff08;熟悉&#xff09; 1.1 基本概念 1.2 主要功能 1.3 访问内置对象的数据 1.3.1访问方式 1.3.2 执行流程 1.4 访问请求参数的数据 1.5 访问Bean对象的属性 1.5.1 访问方式 1.5.2 主要区别 1.6 访问集合中的数据 1.7 常用的内置对象 …

uboot启动流程-涉及lowlevel_init汇编函数

一. uboot启动流程涉及函数 之前文章简单分析了 uboot启动流程的开始&#xff0c;从链接脚本文件 u-boot.lds 中&#xff0c;我们已经知道了入口点是 arch/arm/lib/vectors.S 文件中的 _start函数。 _start函数&#xff1a;调用了 reset 函数&#xff0c;reset 函数内部&…