代码随想录算法训练营第五十二天 |动态规划 part13

300. 最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp[i] 表示以nums[i]结尾的最长递增子序列
        int[] dp = new int[n];
        // 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
        // 初始化为1
        Arrays.fill(dp,1);
        for (int i = 0; i < dp.length; i++) {
            // 比i小的dp[j]最大值
            for(int j = 0; j < i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int i =0; i<dp.length;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

 674.最长连续递增子序列

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-continuous-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        // dp[i] 表示以nums[i]结尾的最长连续递增子序列
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int max = 1;
        for(int i =1;i<n;i++){
            dp[i] = nums[i]<=nums[i-1]?1:dp[i-1]+1;
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

 718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 

 

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        // dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
        // 以i-1, j-1结尾比较好操作
        int[][] dp = new int[len1+1][len2+1];
        // 初始化
        // 根据dp[i][j]的定义,dp[i][0] 和dp[0][j]其实都是没有意义 -> 设为0
        // 加入nums1[0] == nums2[0]
        // 那么dp[1][1] = dp[0][0] +1 = 1符合逻辑
        int res = 0;
        for(int i =1;i<len1+1;i++){
            for(int j=1;j<len2+1;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = Math.max(res,dp[i][j]);
                }
            }
        }

        return res;
    }
}

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

作业区域工服穿戴识别算法 yolov7

作业区域工服穿戴识别系统基于yolov7视频智能图像识别技术&#xff0c;作业区域工服穿戴识别算法模型利用深度学习技术&#xff0c;不需人为干预自动识别现场施工作业人员未按要求穿工作服行为&#xff0c;代替后台工作人员执勤时的人眼判断。YOLOv7 研究团队提出了基于 ELAN 的…

浅谈网络流

网络流 流网络&#xff1a; G ( V , E ) G(V,E) G(V,E)是一个有向图&#xff0c;网络中有两个特殊点&#xff1a;源点s与汇点t。容量用 c c c表示&#xff0c;流量用 f f f表示 流网络G中满足两个性质&#xff1a;1、容量限制(通过一条边的流量不会超过该边的容量)&#xff…

音视频技术开发周刊 | 291

每周一期&#xff0c;纵览音视频技术领域的干货。 新闻投稿&#xff1a;contributelivevideostack.com。 谷歌将 AI 芯片团队并入云计算部门 追赶微软和亚马逊 OpenAI推出的ChatGPT获得一定成功&#xff0c;微软是OpenAI的重要投资者&#xff0c;它将ChatGPT植入必应搜索&#…

基于STATCOM的风力发电机稳定性问题仿真分析(Simulink)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

thinkphp6 JWT报错 ‘“kid“ empty, unable to lookup correct key‘解决办法

文章目录 JWT简介安装问题先前的代码解决办法修改后的完整代码 JWT简介 JWT全称为Json Web Token&#xff0c;是一种用于在网络应用之间传递信息的简洁、安全的方式。JWT标准定义了一种简洁的、自包含的方法用于通信双方之间以JSON对象的形式安全的传递信息。由于它的简洁性、可…

关于SpringBoot整合Websocket实现简易对话聊天窗

前言 官网链接&#xff1a;Websocket Websocket 是什么&#xff1f;它可以将两个独立的浏览器窗口作为通信的两端。 这种形式的通信与传统的 HTTP、TCP 所不同。传统的 HTTP 请求—响应协议是无法实现实时通信的&#xff0c;也就是说&#xff0c;只能由客户端向服务端发送请求…

英语中主语从句的概念及其用法,例句(不断更新)

主语从句的原理 主语从句是一种充当整个句子主语的从句&#xff0c;主语从句构成的句子&#xff0c;是要以引导词开头的。它可以用名词性从属连词、关系代词或关系副词引导。主语从句通常位于谓语动词之前&#xff0c;用于表示动作、状态或事件的主体。 以下是一些常用的引导主…

MiniGPT-4,开源了!

上个月GPT-4发布时&#xff0c;我曾写过一篇文章分享过有关GPT-4的几个关键信息。 当时的分享就提到了GPT-4的一个重要特性&#xff0c;那就是多模态能力。 比如发布会上演示的&#xff0c;输入一幅图&#xff08;手套掉下去会怎么样&#xff1f;&#xff09;。 GPT-4可以理解…

推荐几个可以免费使用的ChatGPT工具

在ChatGPT相关API推出之后&#xff0c;各种工具如雨后春笋一般层出不穷&#xff0c;这篇文章就列举一些日常使用到的工具。 工具列表 OpenAI 在线读取任意网页内容包括视频&#xff08;YouTube&#xff09;&#xff0c;并根据这些内容回答你提出的相关问题或总结相关内容支持…

Mysql-视图

视图 视图介绍视图的语法视图的检查选项CASCADEDLOCAL 视图的更新视图的作用 视图介绍 视图&#xff08;View&#xff09;是一种虚拟存在的表。视图中的数据并不在数据库中实际存在&#xff0c;行和列数据来自定义视图的查询中使用的表&#xff0c;并且是在使用视图时动态生成的…

【配电网优化】基于串行和并行ADMM算法的配电网优化研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

2023年值得关注的20大网络安全趋势

随着围绕所有企业的数字革命&#xff0c;无论大小&#xff0c;企业、组织甚至政府都依赖计算机化系统来管理他们的日常活动&#xff0c;从而使网络安全成为保护数据免受各种在线攻击或任何未经授权访问的主要目标。 随着数据泄露、勒索软件和黑客攻击的新闻成为常态&#xff0…

java获取文件夹下所有文件名

在进行 Java编程的过程中&#xff0c;我们会经常使用到文件夹下的所有文件名。有时候可能不太熟悉 Java编程的小伙伴们会发现&#xff0c;在代码中没有获取到所有的文件名&#xff0c;那么这个时候我们应该怎么去获取到这些文件呢&#xff1f;在进行 Java编程的过程中&#xff…

深度学习卷积神经网络学习小结

————————————————————————————————————————————— 学习小结&#xff1a; 1&#xff09;深度学习综述&#xff1b;&#xff08;2&#xff09;对卷积神经网络&#xff08;CNN&#xff09;的认识&#xff1b;&#xff08;3&#xff0…

08 Kubernetes应用配置管理

课件 在 Kubernetes 中&#xff0c;secret 是一种用于存储敏感信息的对象。Kubernetes 支持以下三种类型的 secret&#xff1a; Opaque&#xff1a;这是默认的 secret 类型&#xff0c;可以用于存储任何类型的数据&#xff0c;包括字符串、二进制数据等。 Service Account&…

Python研究生组蓝桥杯(省二)参赛感受

为什么参加蓝桥杯&#xff1f; 今年是读研的第一年&#xff0c;看着我简历上的获奖经历“优秀学生干部”“优秀志愿者”“优秀毕业生”......大学四年&#xff0c;我竟然没有一次竞赛类的经历&#xff0c;也没有拿得出手的项目&#xff0c;我陷入了深深的焦虑。 听说蓝桥杯的…

[架构之路-183]-《软考-系统分析师》-13-系统设计 - 高内聚低耦合详解、图解以及技术手段

目录 第1章 什么是高内聚低耦合 1.1 概念 1.2 目的 1.3 什么时候需要进行高内聚低耦合 1.4 什么系统需要关注高内聚、低耦合 第2章 分类 2.1 内聚的分类 2.2 耦合的分类 第3章 增加高内聚降低耦合度的方法 3.1 增加高内聚 3.2 降低耦合度 第1章 什么是高内聚低耦…

超详细的R语言svykm函数绘制复杂抽样设计数据cox回归生存曲线(Kaplan-Meier)

我们在既往的文章《R语言绘制复杂抽样设计数据cox回归生存曲线(Kaplan-Meier)》中介绍了怎么使用jskm包的svykm函数绘制复杂抽样设计数据cox回归生存曲线(Kaplan-Meier)&#xff0c;但是有粉丝觉得讲得不够详细&#xff0c;希望讲得详细一点&#xff0c;今天我们继续来介绍一下…

排序算法 — 归并排序

文章目录 归并排序介绍从下往上的归并排序从上往下的归并排序 归并排序实现从上往下的归并排序从下往上的归并排序 归并排序的时间复杂度和稳定性归并排序时间复杂度归并排序稳定性 代码实现核心&总结 每日一道算法&#xff0c;提高脑力。第五天(时隔7天&#xff0c;终于回…

Mybatis 框架 ( 一 ) 基本步骤

1.概念 1.1.什么是Mybatis框架 &#xff08;1&#xff09;Mybatis是一个半ORM&#xff08;Object Relation Mapping 对象关系映射&#xff09;框架&#xff0c;它内部封装了JDBC&#xff0c;开发时只需要关注SQL语句本身&#xff0c;不需要花费精力去处理加载驱动、创建连接、…
最新文章