【算法优选】 动态规划之子数组、子串系列——壹

文章目录

  • 🎋前言
  • 🎋最大子数组和
    • 🚩题目描述
    • 🚩算法思路
    • 🚩代码实现
  • 🌴环形子数组的最大和
    • 🚩题目描述
    • 🚩算法思路：
    • 🚩代码实现
  • 🌲乘积最大子数组
    • 🚩题目描述
    • 🚩算法思路：
    • 🚩代码实现
  • ⭕总结

🎋前言

动态规划相关题目都可以参考以下五个步骤进行解答：

  1. 状态表示

  2. 状态转移⽅程

  3. 初始化

  4. 填表顺序

  5. 返回值

后面题的解答思路也将按照这五个步骤进行讲解。

🎋最大子数组和

🚩题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

  • 示例 1：
    输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
  • 示例 2：
    输入：nums = [1]
    输出：1
  • 示例 3：
    输入：nums = [5,4,-1,7,8]
    输出：23
class Solution {
    public int maxSubArray(int[] nums) {

    }
}

🚩算法思路

  1. 状态表示：

对于线性 dp ，我们可以⽤「经验 + 题⽬要求」来定义状态表示：

  • 以某个位置为结尾，进行一系列操作；
  • 以某个位置为起点，进行一系列操作。

这⾥我们选择比较常用的方式，以「某个位置为结尾」，结合「题目要求」，定义⼀个状态表示：

dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和。

  1. 状态转移⽅程：

dp[i] 的所有可能可以分为以下两种：

  • 子数组的长度为 1 ：此时 dp[i] = nums[i] ；
  • 子数组的长度⼤大于 1 ：此时 dp[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和 的最⼤值再加上 nums[i] ，也就是 dp[i - 1] + nums[i] 。

由于我们要的是「最大值」，因此应该是两种情况下的最⼤值，因此可得转移⽅程：

  • dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
  1. 初始化：

可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：

  • 辅助结点里面的值要「保证后续填表是正确的」；
  • 「下标的映射关系」。

在本题中，最前⾯加上⼀个格⼦，并且让 dp[0] = 0 即可。

  1. 填表顺序

根据「状态转移⽅程」易得，填表顺序为「从左往右」。

  1. 返回值：

状态表示为「以 i 为结尾的所有⼦数组」的最⼤值，但是最大子数组和的结尾我们是不确定的。

因此我们需要返回整个 dp 表中的最⼤值。

🚩代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length + 1];
        int ret = Integer.MIN_VALUE;
        for (int  i = 1; i < dp.length; i++) {
            dp[i] = Math.max(nums[i -1],dp[i - 1] + nums[i - 1]);
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}

在这里插入图片描述

🌴环形子数组的最大和

🚩题目描述

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

  • 示例 1：
    输入：nums = [1,-2,3,-2]
    输出：3
    解释：从子数组 [3] 得到最大和 3
  • 示例 2：
    输入：nums = [5,-3,5]
    输出：10
    解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
  • 示例 3：
    输入：nums = [3,-2,2,-3]
    输出：3
    解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
class Solution {
    public int maxSubarraySumCircular(int[] nums) {

    }
}

🚩算法思路：

本题与「最大子数组和」的区别在于，考虑问题的时候不仅要分析「数组内的连续区域」，还要考虑「数组⾸尾相连」的⼀部分。结果的可能情况分为以下两种：

  1. 结果在数组的内部，包括整个数组；
  2. 结果在数组首尾相连的⼀部分上。

其中，对于第⼀种情况，我们仅需按照「最大子数组和」的求法就可以得到结果，记为 fmax 。

对于第⼆种情况，我们可以分析⼀下：

  • 如果数组⾸尾相连的⼀部分是最⼤的数组和，那么数组中间就会空出来⼀部分；
  • 因为数组的总和 sum 是不变的，那么中间连续的⼀部分的和⼀定是最小的；

因此，我们就可以得出⼀个结论，对于第⼆种情况的最⼤和，应该等于 sum - gmin ，其中gmin 表⽰数组内的「最⼩⼦数组和」。

两种情况下的最⼤值，就是我们要的结果。

但是，由于数组内有可能全部都是负数，第⼀种情况下的结果是数组内的最⼤值（是个负数），第⼆种情况下的 gmin == sum ，求的得结果就会是 0 。

若直接求两者的最⼤值，就会是 0 。但是实际的结果应该是数组内的最⼤值。对于这种情况，我们需要特殊判断⼀下。

由于「最⼤⼦数组和」的⽅法已经讲过，这⾥只提⼀下「最⼩⼦数组和」的求解过程，其实与「最⼤⼦数组和」的求法是⼀致的。⽤ f 表⽰最⼤和， g 表⽰最⼩和。

  1. 状态表示：

g[i] 表⽰：以 i 做结尾的「所有⼦数组」中和的最⼩值。

  1. 状态转移⽅程：

g[i] 的所有可能可以分为以下两种：

  1. ⼦数组的⻓度为 1 ：此时 g[i] = nums[i] ；
  2. ⼦数组的⻓度⼤于 1 ：此时 g[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和的最⼩值再加上 nums[i] ，也就是 g[i - 1] + nums[i] 。

由于我们要的是最⼩⼦数组和，因此应该是两种情况下的最⼩值，因此可得转移⽅程：

  • g[i] = min(nums[i], g[i - 1] + nums[i]) 。
  1. 初始化：
    可以在最前⾯加上⼀个辅助结点，帮助我们初始化。使⽤这种技巧要注意两个点：

  • 辅助结点⾥⾯的值要保证后续填表是正确的；

  • 下标的映射关系。

在本题中，最前⾯加上⼀个格⼦，并且让 g[0] = 0 即可。

  1. 填表顺序：

根据状态转移⽅程易得，填表顺序为「从左往右」。

  1. 返回值：
  • 先找到 f 表⾥⾯的最⼤值 -> fmax ；
  • 找到 g 表⾥⾯的最⼩值 -> gmin ；
  • 统计所有元素的和 -> sum ；
  • 返回 sum == gmin ? fmax : max(fmax, sum - gmin)

🚩代码实现

    public int maxSubarraySumCircular(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        int sum = 0;
        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            f[i] = Math.max(x, x + f[i - 1]);
            fmax = Math.max(fmax, f[i]);
            g[i] = Math.min(x, x + g[i - 1]);
            gmin = Math.min(gmin, g[i]);
            sum += x;
        }
        return sum == gmin ? fmax : Math.max(fmax, sum - gmin);
    }

在这里插入图片描述

🌲乘积最大子数组

🚩题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续

子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

  • 示例 1:
    输入: nums = [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。
  • 示例 2:
    输入: nums = [-2,0,-1]
    输出: 0
    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
class Solution {
    public int maxProduct(int[] nums) {

    }
}

🚩算法思路：

这道题与「最大子数组和] 非常相似，我们可以效仿着定义⼀下状态表⽰以及状态转移：

  • dp[i] 表示以 i 为结尾的所有子数组的最⼤乘积，
  • dp[i] = max(nums[i], dp[i - 1] * nums[i]) ；

由于正负号的存在，我们很容易就可以得到，这样求 dp[i] 的值是不正确的。因为 dp[i - 1] 的信息并不能让我们得到 dp[i] 的正确值。

比如数组 [-2, 5, -2] ，用上述状态转移得到的 dp数组为 [-2, 5, -2] ，最⼤乘积为 5 。但是实际上的最⼤乘积应该是所有数相乘，结果为 20 。

究其原因，就是因为我们在求 dp[2] 的时候，因为 nums[2] 是⼀个负数，因此我们需要的是「 i - 1 位置结尾的最⼩的乘积 （-10） 」，这样⼀个负数乘以「最⼩值」，才会得到真实的最⼤值。

因此，我们不仅需要⼀个「乘积最⼤值的 dp 表」，还需要⼀个「乘积最⼩值的 dp 表」。

  1. 状态表⽰：

f[i] 表⽰：以 i 结尾的所有⼦数组的最⼤乘积，
g[i] 表⽰：以 i 结尾的所有⼦数组的最⼩乘积。

  1. 状态转移⽅程：

遍历每⼀个位置的时候，我们要同步更新两个 dp 数组的值。

对于 f[i] ，也就是「以 i 为结尾的所有⼦数组的最⼤乘积」，对于所有⼦数组，可以分为下⾯三种形式：

  • ⼦数组的⻓度为 1 ，也就是 nums[i] ；
  • ⼦数组的⻓度⼤于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有⼦数组的最⼤乘积 f[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；
  • ⼦数组的⻓度⼤于 1 ，但 nums[i] < 0 ，此时需要的是 i - 1 为结尾的所有⼦数组的最⼩乘积 g[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；（如果 nums[i] = 0 ，所有⼦数组的乘积均为 0 ，三种情况其实都包含了）

综上所述， f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i -
1]) )。

对于 g[i] ，也就是「以 i 为结尾的所有⼦数组的最⼩乘积」，对于所有⼦数组，可以分为下⾯三种形式：

  • 子数组的⻓度为 1 ，也就是 nums[i] ；
  • 子数组的⻓度⼤于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有子数组的最⼩乘积 g[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；
  • 子数组的长度度⼤于 1 ，但 nums[i] < 0 ，此时需要的是 i - 1 为结尾的所有子数组的最⼤乘积 f[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；

综上所述， g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1])) 。
（如果 nums[i] = 0 ，所有⼦数组的乘积均为 0 ，三种情况其实都包含了）

  1. 初始化：

可以在最前面加上⼀个辅助结点，帮助我们初始化。使⽤这种技巧要注意两个点：

  • 辅助结点里面的值要保证后续填表是正确的；
  • 下标的映射关系。

在本题中，最前⾯加上⼀个格⼦，并且让 f[0] = g[0] = 1 即可。

  1. 填表顺序：

根据状态转移⽅程易得，填表顺序为「从左往右，两个表⼀起填」。

  1. 返回值：

返回 f 表中的最⼤值

🚩代码实现

class Solution {
    public int maxProduct(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = 1;
        g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int y = f[i - 1] * nums[i - 1];
            int z = g[i - 1] * nums[i - 1];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}

在这里插入图片描述

⭕总结

关于《【算法优选】 动态规划之子数组、子串系列——壹》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

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

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

相关文章

【PostgreSQL支持中文的全文检索插件(zhparser)】

【PostgreSQL支持中文的全文检索插件(zhparser)】

PostgreSQL本身是支持全文检索的&#xff0c;提供两个数据类型&#xff08;tsvector,tsquery&#xff09;&#xff0c;并且通过动态检索自然语言文档的集合&#xff0c;定位到最匹配的查询结果。其内置的默认的分词解析器采用空格进行分词&#xff0c;但是因为中文的词语之间没…
阅读更多...
想要安装Word、Excel、PowerPoint，但却找不到对应软件？

想要安装Word、Excel、PowerPoint，但却找不到对应软件？

前言 前几天有小伙伴在找Word和Excel软件&#xff0c;但找了半天都没发现怎么安装。 这件事情其实很简单&#xff0c;那就是Word、Excel并不是单独的一个个软件&#xff0c;而是集成在MS Office套件里的。 咱们大部分人常用的办公软件大概是Word、Excel和PowerPoint这三个。还…
阅读更多...
保研机试之【设备驱动程序】

保研机试之【设备驱动程序】

B选项&#xff1a; 综上&#xff0c;我认为这道题选择D~
阅读更多...
Host is not allowed to connect to this MySQL server解决方法

Host is not allowed to connect to this MySQL server解决方法

在阿里云服务器上安装了Mysql数据库&#xff0c;在阿里云上使用一切正常。我用navicat 去连接服务器时显示Host is not allowed to connect to this MySQL server。 ​ 看见这个错误&#xff0c;第一反应是是不是阿里云服务器防火墙没有配置mysq的出入站规则。去阿里云检查了一…
阅读更多...
Day 46 139.单词拆分

Day 46 139.单词拆分

单词拆分 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict&#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明&#xff1a; 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1&#xff1a; 输入: s “leet…
阅读更多...
Nginx配置Referer防盗链

Nginx配置Referer防盗链

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 HTTP Referer是Hea…
阅读更多...
ASP.NET银行大厅自助信息系统的开发与实现

ASP.NET银行大厅自助信息系统的开发与实现

摘 要 本毕业设计在基于银行业务大厅现有业务的基础上&#xff0c;针对自助银行的概念和其独有特点&#xff0c;通过.NETSQL技术&#xff0c;开发一个简单的银行大厅自助信息系统&#xff0c;完成一些自助银行的业务需求如帐户信息查询、帐户挂失、自助交费、留言、新闻查询…
阅读更多...
惠普发布全新AI战略，重塑办公空间 引领企业智能化新浪潮

惠普发布全新AI战略，重塑办公空间 引领企业智能化新浪潮

近日、全球知名科技公司惠普在北京隆重举办了以“用智能&#xff0c;开启无限可能”为主题的2024惠普商用AI战略暨AI PC新品发布会&#xff0c;此次盛会标志着惠普在人工智能领域迈出了重要一步&#xff0c;惠普紧跟时代步伐&#xff0c;推出了更高效、更安全、更灵活的AI PC产…
阅读更多...
AI与人类生活的融合：安克创新CEO阳萌的深度洞见

AI与人类生活的融合：安克创新CEO阳萌的深度洞见

安克创新CEO阳萌分享了他对人工智能未来发展的深刻见解。阳萌不仅深入探讨了大模型技术的应用前景&#xff0c;还对AI与人类生活的融合提出了引人入胜的思考。以下是对这次访谈内容的总结和分析。 大模型技术的现实应用 阳萌提到&#xff0c;尽管大模型在处理通用知识方面表…
阅读更多...
huggingface 笔记：pipeline

huggingface 笔记：pipeline

1 介绍 pipeline() 是使用预训练模型进行推理的最简单和最快速的方式。可以针对不同模态的许多任务直接使用 pipeline() 2 举例&#xff1a;情感分析 2.1 创建pipeline实例 from transformers import pipelineclassifier pipeline("sentiment-analysis") #首先创…
阅读更多...
[Java EE] 文件IO (二):文件内容读写-----数据流

[Java EE] 文件IO (二):文件内容读写-----数据流

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏:&#x1f355; Collection与数据结构 (91平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 &#x1f9c0;Java …
阅读更多...
使用 RyTuneX 增强您的 Windows 10 和 11 体验 – Rayen Ghanmi 的首选优化器。

使用 RyTuneX 增强您的 Windows 10 和 11 体验 – Rayen Ghanmi 的首选优化器。

&#x1f4dd; 关于 RyTuneX 是使用 WinUI 3 框架构建的尖端优化器&#xff0c;旨在增强 Windows 设备&#x1f680;的性能。 RyTuneX 专为 Windows 10 和 11 打造&#xff0c;使用户能够毫不费力地删除顽固的预装应用程序并优化系统资源&#x1f6e0;️。 &#x1f680; 功能…
阅读更多...
在线caj转换成pdf免费吗？caj变成pdf很容易！点进来！

在线caj转换成pdf免费吗？caj变成pdf很容易！点进来！

在数字化阅读日益盛行的今天&#xff0c;各种电子文献格式层出不穷&#xff0c;其中CAJ和PDF无疑是两种最为常见的格式。CAJ是中国知网推出的一种专用全文阅读格式&#xff0c;而PDF则因其跨平台、不易被修改的特性&#xff0c;受到了广大读者的青睐。因此&#xff0c;将CAJ格式…
阅读更多...
【Kibana】快速上手Kibana平台（KQL）

【Kibana】快速上手Kibana平台（KQL）

文章目录 快速使用Kibana平台常用查询语句KQL基本查询覆合查询模糊查询 目前市面上大部分的公司的日志系统都是使用ELK系统&#xff0c;因此我们进行工作必须得掌握Kibana平台的基本使用&#xff0c;这里主要说明怎么“快速使用Kibana平台”以及记录一些常用的“KQL语言”。 快…
阅读更多...
鸿蒙内核源码分析(消息封装篇) | 剖析LiteIpc(上)进程通讯内容

鸿蒙内核源码分析(消息封装篇) | 剖析LiteIpc(上)进程通讯内容

基本概念 LiteIPC是OpenHarmony LiteOS-A内核提供的一种新型IPC&#xff08;Inter-Process Communication&#xff0c;即进程间通信&#xff09;机制&#xff0c;为轻量级进程间通信组件&#xff0c;为面向服务的系统服务框架提供进程间通信能力&#xff0c;分为内核实现和用户…
阅读更多...
centos7中如何优雅的动态切换jdk版本？

centos7中如何优雅的动态切换jdk版本？

在 CentOS 7 中动态切换 JDK 版本可以通过多种方法实现&#xff0c;其中最常见的方法是使用 alternatives 命令&#xff0c;这是 CentOS 和其他基于 Red Hat 的系统中用于管理多个软件版本的标准工具。下面我会详细介绍如何使用 alternatives 命令来切换 JDK 版本。 步骤 1: 安…
阅读更多...
【QuikGraph】C#调用第三方库计算有向图、无向图的连通分量

【QuikGraph】C#调用第三方库计算有向图、无向图的连通分量

QuikGraph库 项目地址&#xff1a;https://github.com/KeRNeLith/QuikGraph 相关概念 图论、连通分量、强连通分量相关概念&#xff0c;可以从其他博客中复习&#xff1a; https://blog.csdn.net/weixin_50564032/article/details/123289611 https://zhuanlan.zhihu.com/p/3…
阅读更多...
记录Spring Boot 2.3.4.RELEASE版注解方式实现AOP和通知的执行顺序

记录Spring Boot 2.3.4.RELEASE版注解方式实现AOP和通知的执行顺序

1.advice 按照以下的顺序执行 输出结果&#xff1a;(正常和异常) 说明&#xff1a;Spring boot 2.3.4.RELEASE 版本使用的AOP是spring-aop-5.2.9.RELEASE&#xff0c;AOP的通知顺序不一样。 可以测试下Spring boot 2.1.1.RELEASE 版做对比&#xff0c;发现结果是不一样的。 2…
阅读更多...
在React中利用Postman测试代码获取数据

在React中利用Postman测试代码获取数据

文章目录 概要名词解释1、Postman2、axios 使用Postman测试API在React中获取并展示数据小结 概要 在Web开发中&#xff0c;通过API获取数据是一项常见任务。Postman是一个功能强大的工具&#xff0c;可以帮助开发者测试API&#xff0c;并查看API的响应数据。在本篇博客中&…
阅读更多...
不懂数字后端Box List、Polygon的意思？

不懂数字后端Box List、Polygon的意思？

什么是BOX&#xff1f; 景芯SoC做design planning的第一步就是确定floorplan的box&#xff0c;也就是设计的区域。这个区域可以划分为三个边界&#xff0c;如下图所示&#xff1a; Die Box 最外面一圈&#xff0c;我们称为 Die Box&#xff0c;也就是用来放置 IO 单元&#x…
阅读更多...
最新文章

Copyright @ 2022~2023