LeedCode刷题---子数组问题

顾得泉:个人主页

个人专栏:《Linux操作系统》  《C/C++》  《LeedCode刷题》

键盘敲烂,年薪百万!


一、最大子数组和

题目链接:最大子数组和 

题目描述

       给你一个整数数组 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

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

解法

1.状态表示:

       对于线性dp,我们可以用「经验+题目要求」来定义状态表示:

       i.以某个位置为结尾,巴拉巴拉;

       ii.以某个位置为起点,巴拉巴拉。

       这里我们选择比较常用的方式,以「某个位置为结尾」

结合「题目要求」,定义一个状态表示:

       dp[i]表示:以i位置元素为结尾的「所有子数组」中和的最大和

2.状态转移方程:

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

        i.子数组的长度为1:此时dpLi= nums[i];

        ii.子数组的长度大于1:此时 dp[i]应该等于以i - 1做结尾的「所有子数组」中和的最大值再加上nums[i],也就是dp[i - 1]+ nums[i]

       由于我们要的是最大值,因此应该是两种情况下的最大值,因此可得转移方程:

       dp[i] = max (nums[i],dp[i - 1]+ nums[i])

3.初始化:

       可以在最前面加上一个「辅助结点」,帮助我们初始化。使用这种技巧要注意两个点:

       i.辅助结点里面的值要「保证后续填表是正确的」;

       ii.「下标的映射关系」

       在本题中,最前面加上一个格子,并且让dp[0] = 即可

4.填表顺序:

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

5.返回值:

       状态表示为「以1为结尾的所有子数组」的最大值,但是最大子数组和的结尾我们是不确定的。因此我们需要返回整个dp表中的最大值

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> dp(n + 1);
        int ret = INT_MIN;
        for(int i = 1; i <= n; i++)
        {
        dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
        ret = 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

提示:

  • n == nums.length
  • 1 <= n <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104

解法

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

       i.结果在数组的内部,包括整个数组;

       ii.结果在数组首尾相连的一部分上

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

       i.如果数组首尾相连的一部分是最大的数组和,那么数组中间就会空出来一部分;

       ii.因为数组的总和sum是不变的,那么中间连续的一部分的和一定是最小的;因此,我们就可以得出一个结论,对于第二种情况的最大和,应该等于sum - gmin

       其中,gmin表示数组内的「最小子数组和」

       两种情况下的最大值,就是我们要的结果

       但是,由于数组内有可能全部都是负数,第一种情况下的结果是数组内的最大值(是个负数),第二种情况下的 gmin == sum,求的得结果就会是0。若直接求两者的最大值,就会是0。但是实际的结果应该是数组内的最大值。对于这种情况,我们需要特殊判断一下

       由于「最大子数组和」的方法已经讲过,这里只提一下「最小子数组和」的求解过程,其实与「最大子数组和」的求法是一致的。用f表示最大和,g表示最小和

1.状态表示:

       g[i]表示:以i做结尾的所有子数组中和的最小值

2.状态转移方程:

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

       i.子数组的长度为1 :此时g[i] = nums[i] ;

       ii.子数组的长度大于1∶此时 g[i应该等于以i - 1做结尾的「所有子数组」中和的最小值再加上nums[i],也就是g[i - 1] + nums[i]

       由于我们要的是最小子数组和,因此应该是两种情况下的最小值,因此可得转移方程:

       g[i] = min( nums[i],g[i - 1]+ nums[i])

3.初始化:

       可以在最前面加上一个辅助结点,帮助我们初始化。使用这种技巧要注意两个点:

       i.辅助结点里面的值要保证后续填表是正确的;

       ii.下标的映射关系

       在本题中,最前面加上一个格子,并且让g[0]= 0即可

4.填表顺序:

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

5.返回值:

        a.先找到f表里面的最大值->fmax ;

        b.找到g表里面的最小值-> gmin ;

        c.统计所有元素的和->sum ;

        d.返回sum == gmin ? fmax : max ( fmax, sum - gmin)

代码实现

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
        for(int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            f[i] = max(x, x + f[i - 1]);
            fmax = max(fmax, f[i]);
            g[i] = min(x, x + g[i - 1]);
            gmin = min(gmin, g[i]);
            sum += x;
        }
        return sum == gmin ? fmax : 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] 不是子数组

提示:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

解法

       这道题与「最大子数组和」非常相似,我们可以效仿着定义一下状态表示以及状态转移:

       i. dp[i]表示以i为结尾的所有子数组的最大乘积,

       ii. 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结尾的所有子数组的最小乘积

2.状态转移方程:

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

       对于f[i],也就是「以为结尾的所有子数组的最大乘积」,对于所有子数组,可以分为下面三种形式:

       i.子数组的长度为1,也就是nums[i] ;

       ii.子数组的长度大于1,但nums[i] > 0,此时需要的是i - 1为结尾的所有子数组的最大乘积f[i - 1],再乘上nums[i],也就是nums[i] * f[i - 1];

       ili.子数组的长度大于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],也就是「以1为结尾的所有子数组的最小乘积」,对于所有子数组,可以分为下面三种形式:

       i.子数组的长度为1,也就是nums[i];   

       ii.子数组的长度大于1),但nums[i] > 0,此时需要的是i – 1为结尾的所有子数组的最小乘积g[i - 1],再乘上nums[i],也就是nums[i] * g[i - 1];

       iii.子数组的长度大于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,三种情况其实都包含了)

3.初始化:

       可以在最前面加上一个辅助结点,帮助我们初始化。使用这种技巧要注意两个点:

       i.辅助结点里面的值要保证后续填表是正确的;

       ii.下标的映射关系。

       在本题中,最前面加上一个格子,并且让f[o]=g[o]=1即可

4.填表顺序:

       根据状态转移方程易得,填表顺序为从左往右,两个表一起填

5.返回值:

       返回f表中的最大值

代码实现

class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for(int i = 1; i <= n; i++)
        {
            int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1];
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

 结语:今日的刷题分享到这里就结束了,希望本篇文章的分享会对大家的学习带来些许帮助,如果大家有什么问题,欢迎大家在评论区留言~~~ 

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

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

相关文章

Microsoft Expression Web - 网页布局

在本章中&#xff0c;我们将介绍网页的基本布局。在创建我们的网页布局之前&#xff0c;我们需要考虑我们的内容&#xff0c;然后设计我们希望如何呈现该内容&#xff0c;因为它是在我们的网站上可见的内容。 由我们如何呈现我们的内容&#xff0c;以便我们的观众找到我们的网…

网络运维与网络安全 学习笔记2023.12.3

网络运维与网络安全 学习笔记 第三十三天 今日目标 目录-文件基本管理、vim文本编辑、用户账号管理 组账号管理、归属控制、权限控制 目录-文件基本管理 ls 列目录及文档属性 ls - List 格式:ls[选项]…[目录或文件路径] 1.如果不以/开始,表示相对路径(省略了当前所在位置…

不得不说,HelpLook真的是一个很懂用户的文档管理工具

在当今互联网时代&#xff0c;信息的爆炸性增长使得有效管理和组织文档变得至关重要。随着企业规模的扩大和团队协作的增加&#xff0c;如何高效地存储、共享和访问关键知识和文档成为了一个难题。不过&#xff0c;我早之前有幸发现&#xff0c;HelpLook这个文档工具是真正懂得…

【计算机视觉】基于OpenCV计算机视觉的摄像头测距技术设计与实现

基于计算机视觉的摄像头测距技术 文章目录 基于计算机视觉的摄像头测距技术导读引入技术实现原理技术实现细节Python-opencv实现方案获取目标轮廓步骤 1&#xff1a;图像处理步骤 2&#xff1a;找到轮廓步骤完整代码 计算图像距离前置技术背景与原理步骤 1&#xff1a;定义距离…

【tensorflow学习-选择动作】 学习tensorflow代码调用过程

a actor.choose_action(s) def choose_action(self, s):s s[np.newaxis, :]return self.sess.run(self.action, {self.s: s}) # get probabilities for all actions输入&#xff1a;s 输出&#xff1a;self.sess.run(self.action, {self.s: s}) &#xff1a;a

【云原生Prometheus篇】Prometheus PromQL语句详解 1.0

文章目录 一、前言1.1 Prometheus的时间序列1.1.1 指标名称1.1.2 标签1.1.3 使用的注意事项 1.2 样本数据格式1.3 Prometheus 的聚合函数 二 、PromQL 理论部分2.1 PromQL简介2.2 PromQL的数据类型2.3 时间序列选择器2.3.1 瞬时向量选择器 &#xff08;Instant Vector Selector…

React使用TailwindCSS

React中使用TailwindCSS TailwindCSS是 下载及初始化 可以查看官网对照自己使用的框架进行配置 npm install -D tailwindcss postcss autoprefixer下载完毕后执行如下命令 npx tailwindcss init -p可以发现项目中多了两个文件 其中默认已经进行了配置&#xff0c;我们需要将…

JSP格式化标签 parseNumber指定格式字符串转数字类型

好 我们继续来说格式化标签 parseNumber 它的作用是讲一个字符串 转换为指定格式的数值型 老实说 这东西 作为了解把 实际开发中都不是用得少 我建议还是在java端就处理好 不建议在jsp中高这种类型转换的操作 基本格式如下 这几个属性都是我们这几期jsp标签的老朋友了 我们…

bean依赖属性配置

bean依赖属性配置 文章目录 bean依赖属性配置 Data ConfigurationProperties(prefix "cartoon") public class CartoonProperties {private Cat cat;private Mouse mouse; }cartoon:cat:name: whatage: 5mouse:name: howage: 6这样的话&#xff0c;业务bean无需在读…

使用AOS实现网页动画效果

在现代Web开发中&#xff0c;动画效果是提升用户体验和页面交互性的重要因素之一。而AOS&#xff08;Animate On Scroll&#xff09;作为一个强大的动画库&#xff0c;可以帮助我们轻松地实现网页元素的滚动动画效果。 什么是AOS&#xff1f; AOS是一个基于CSS3和JavaScript的…

[C/C++]数据结构 关于二叉树的OJ题(利用分治思想解决难题)

题目一: 单值二叉树 &#x1f6a9;⛲&#x1f31f;⚡&#x1f966;&#x1f4ac; &#x1f6a9;题目链接:力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 ⛲题目描述: 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。…

docker部署typecho博客

文章目录 1.安装git2.安装compose3.拉取仓库4.创建目录5.配置文件修改6.启动容器7.修改MYSQL数据库8.安装成功9.参考GitHub文档 1.安装git 安装git yum -y install git2.安装compose &#xff08;docker安装参考&#xff1a;docker基本知识&#xff09; 确保已经安装了 Doc…

如何捕捉股票短线机会

一、个股相关新闻 1、盈利变化 当公司的盈利能力提升时&#xff0c;投资者就会积极地买入该股&#xff0c;股价短期内会上升。尤其是财报即将发布的阶段&#xff0c;那些能够盈利预增的股票往往会受到投资者青睐&#xff0c;使股价在短时间内大幅上涨。 比如&#xff0c;2022年…

【C++】类和对象——explicit关键字,友元和内部类

这篇博客已经到了类和对象的最后一部分了&#xff0c;下面我们先看一下explicit关键字 我们还是先来引入一个例子&#xff0c;我们的代码是可以这么写的 class A { public:A(int aa 0) {_a aa;cout << "A(int aa 0)" << endl;} private:int _a; }; i…

Python读取栅格遥感影像并加以辐射校正后导出为Excel的一列数据

本文介绍基于Python语言中的gdal模块&#xff0c;读取一景.tif格式的栅格遥感影像文件&#xff0c;提取其中每一个像元的像素数值&#xff0c;对像素值加以计算&#xff08;辐射定标&#xff09;后&#xff0c;再以一列数据的形式将计算后的各像元像素数据保存在一个.csv格式文…

llama.cpp部署通义千问Qwen-14B

llama.cpp是当前最火热的大模型开源推理框架之一&#xff0c;支持了非常多的LLM的量化推理&#xff0c;生态比较完善&#xff0c;是个人学习和使用的首选。最近阿里开源了通义千问大语言模型&#xff0c;在众多榜单上刷榜了&#xff0c;是当前最炙手可热的开源中文大语言模型。…

使用postman请求x5接口

x5接口简介 1.接口样例 {"header"{"appid":"bpmnew_fanwei","sign":"C033162E86E4CADE80C7EB44D68A5AD2","sign_type":"md5","url":"https://oa.mioffice.cn/api/bpm/xm/app/show/tod…

Java线程安全问题

一、共享资源 共享资源是指&#xff0c;同时会有多个线程访问的资源。 二、线程安全问题 线程安全问题是指多个线程同时读写共享资源时并且没有任何同步措施的情况下&#xff0c;出现脏数据或者其他不可预见的结果的问题。当然如果所有线程都只是读取共享资源而不去修改共享…

LTO编译器优化介绍以及开启方法

文章目录 LTO介绍LTO 开启方法 LTO介绍 LTO&#xff08;Link Time Optimization&#xff0c;链接时优化&#xff09;是一种在链接阶段进行优化的技术。传统的编译过程中&#xff0c;编译器仅能对单个编译单元进行优化。LTO 允许编译器看到跨编译单元的代码&#xff0c;从而进行…

实战案例:chatglm3 基础模型多轮对话微调

chatglm3 发布了&#xff0c;这次还发了base版本的模型&#xff0c;意味着我们可以基于这个base模型去自由地做SFT了。 本项目实现了基于base模型的SFT。 base模型 https://huggingface.co/THUDM/chatglm3-6b-base由于模型较大&#xff0c;建议离线下载后放在代码目录&#…