每日一题 ~乘积最大子数组

 

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/maximum-product-subarray/description/
题目分析

题目要求找出给定整数数组中乘积最大的连续子数组,并返回这个乘积。

思路分析

这道题可以使用动态规划来解决。关键是维护两个状态数组 fg,其中:

  • f[i] 表示以第 i 个元素结尾的最大子数组乘积;
  • g[i] 表示以第 i 个元素结尾的最小子数组乘积。

为什么需要维护最小值 g[i] 呢?因为负数乘以负数会变成正数,所以需要同时维护最大值和最小值来应对乘积的变化情况。

状态转移方程

对于第 i 个元素:

  • f[i] 的计算方式:
    • f[i] = max(nums[i], f[i-1] * nums[i], g[i-1] * nums[i])
    • 即当前元素自身、前一个最大乘积乘以当前元素、前一个最小乘积乘以当前元素的最大值。
  • g[i] 的计算方式:
    • g[i] = min(nums[i], f[i-1] * nums[i], g[i-1] * nums[i])
    • 即当前元素自身、前一个最大乘积乘以当前元素、前一个最小乘积乘以当前元素的最小值。

初始化

初始状态为:

  • f[0] = nums[0]
  • g[0] = nums[0]

最终结果

最终结果即 f 数组中的最大值,即为整个数组中乘积最大的连续子数组的乘积。

代码实现 

package study1.day12;
/*
*152. 乘积最大子数组
*       思路分析:
*             1.状态表示 f[i]以i位置为结尾的最大子数组的和
*                       g[i]以j位置为结尾的最小子数组的和
*                           在最大值中 > 0 乘最大值   < 0 乘最小值
*             2.状态转移方程 f[i] = max(sum[i],sum[i] * f[i - 1],sum[i] * g[i - 1])
*                           在最小值中 > 0 乘最最小值   < 0 乘最大值
*                          g[i] = min(sum[i],sum[i] * g[i - 1],sum[i] * f[i - 1])
*             3.初始化 f[0] = 1  g[0] = 1 (任何数 * 1都等于任何数)*
*           总结一下: 本题主要是两个dp一个记录最大 一个记录最小
*                       因为本题存在负数当为负数的时候最大值就会变成最小值然后再转换
*                       所以本题一定要分正数在划分一下dp的最小状态
* */
public class test5 {public int maxProduct(int[] nums) {int n = nums.length;//1.创建f g 数组用来存储历史记录int[] f = new int[n];int[] g = new int[n];//2.初始化f[0] = g[0] = 1;int retMax = Integer.MIN_VALUE;//3.填表for (int i = 1; i <= n; i++) {f[i] = Math.max(Math.max(nums[i - 1],f[i - 1] * nums[i - 1]),g[i - 1] * nums[i - 1]);retMax = Math.max(retMax,f[i]);g[i] = Math.min(Math.min(nums[i - 1],g[i - 1] * nums[i - 1]),f[i - 1] * nums[i - 1]);}return retMax;}
}

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

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

相关文章

基于SpringBoot+Vue的热门网游推荐网站(带1w+文档)

基于SpringBootVue的热门网游推荐网站(带1w文档) 基于SpringBootVue的热门网游推荐网站(带1w文档) 本系统选用B/S结构开发&#xff0c;它是一个提供可以对热门网游推荐进行信息管理的系统&#xff0c;用户可以在该系统获取最新动态&#xff0c;可以结识更多的朋友&#xff0c;产…

基于级联深度学习算法在双参数MRI中检测前列腺病变的评估| 文献速递-AI辅助的放射影像疾病诊断

Title 题目 Evaluation of a Cascaded Deep Learning–based Algorithm for Prostate Lesion Detection at Biparametric MRI 基于级联深度学习算法在双参数MRI中检测前列腺病变的评估 Background 背景 Multiparametric MRI (mpMRI) improves prostate cancer (PCa) dete…

SDK 多版本管理控制利器 SDKMAN 介绍及使用

一、SDKMAN 假如你同时参与了一个使用JDK 8的项目和一个采用JDK 17特性的项目。每次在两个项目之间切换时&#xff0c;你都面临着版本冲突的问题。如果有那么一个工具类似于 Python 中的 anaconda 工具&#xff0c;可以帮助你管理不同版本的 SDK &#xff0c;是不是非常有用&a…

八股文无用?也许是计算机大学生的重要人生指南!

大家所说的"八股文"其实指的是那些固定、标准化的面试问题和答案&#xff0c;通常涉及特定的知识点和技术概念。 博主本人也是一枚大学生&#xff0c;个人也记背过相关的八股文&#xff0c;比如计算机网络里的TCP和UDP的区别、TCP三次握手和四次挥手的具体过程等等&a…

汽车电子KL15,KLR,KL30等术语解释

KL作为术语&#xff0c;是德语’klemme’的缩写&#xff0c;代表连接器或连接 缩略词解释KL15汽车电源的RUN模式KL50汽车电源的Crank模式KLR汽车电源的ACC模式KL30汽车蓄电池的正极&#xff0c;始终保持带电状态KL31汽车蓄电池的负极&#xff0c;持续与车辆接地连接KL4048V汽车…

遇到Websocket就不会测了?别慌,学会这个Jmeter插件轻松解决....

websocket 是一种双向通信协议&#xff0c;在建立连接后&#xff0c;websocket服务端和客户端都能主动向对方发送或者接收数据&#xff0c;而在http协议中&#xff0c;一个request只能有一个response&#xff0c;而且这个response也是被动的&#xff0c;不能主动发起。 websoc…

OpenCV C++的网络实时视频流传输——基于Yolov5 face与TCP实现实时推流的深度学习图像处理客户端与服务器端

前言 在Windows下使用TCP协议&#xff0c;基于OpenCV C与Yolov5实现了一个完整的实时推流的深度学习图像处理客户端与服务器端&#xff0c;为了达到实时传输的效果&#xff0c;客户端使用了多线程的方式实现。深度学习模型是基于onnxruntime的GPU推理。&#xff0c;实现效果如…

微服务架构三大利器:限流、降级与熔断

文章目录 前言一、限流&#xff08;Rate Limiting&#xff09;二、降级&#xff08;Degradation&#xff09;三、熔断&#xff08;Circuit Breaker&#xff09;四、三者关系总结 前言 限流、降级和熔断是分布式系统中常用的容错策略&#xff0c;它们各自承担着不同的角色&#…

干货 | 2024中国联通算力网络安全白皮书(免费下载)

本白皮书以国家整体安全观为指导&#xff0c;充分发挥网络安全现代产业链链长的主体支撑和融通带动作用&#xff0c;提出算力网络“新质安全、共链可信”的安全愿景和“构建开放融合内生免疫弹性健壮网安智治的一体化安全”的安全目标。从运营商开展网络建设和应用部署的角度出…

WebWorker处理百万数据

Home.vue <template><el-input v-model"Val" style"width: 400px"></el-input><el-button click"imgHandler">过滤</el-button><hr /><canvas id"myCanvas" width"500" height&quo…

Linux系统之DHCP服务配置

1、准备阶段 Windows&#xff08;客户端&#xff09;开启Vmnet8网卡Linux6&#xff08;服务端&#xff09;网络连接选择NAT模式&#xff0c;并配置IP地址为192.168.11.1/24Linux5&#xff08;客户端&#xff09;网络连接选择NAT模式将NAT的DHCP功能取消 2、DHCP服务器相关软件…

宝塔部署springboot vue ruoyi前后端分离项目,分离lib、resources

1、“文件”中创建好相关项目目录,并将项目相关文件传到对应目录 例如&#xff1a;项目名称/ #项目总目录 api/ #存放jar项目的Java项目文件 manage/ #vue管理后端界面 …

Vue3_对接声网实时音视频_多人视频会议

目录 一、声网 1.注册账号 2.新建项目 二、实时音视频集成 1.声网CDN集成 2.iframe嵌入html 3.自定义UI集成 4.提高进入房间速度 web项目需要实现一个多人会议&#xff0c;对接的声网的灵动课堂。在这里说一下对接流程。 一、声网 声网成立于2014年&#xff0c;是全球…

ARCGIS PRO DSK GraphicsLayer创建文本要素

一、判断GraphicsLayer层【地块注记】是否存在&#xff0c;如果不存在则新建、如果存在则删除所有要素 Dim GraphicsLayer pmap.GetLayersAsFlattenedList().OfType(Of ArcGIS.Desktop.Mapping.GraphicsLayer).FirstOrDefault() 获取当前map对象中的GetLayer图层 Await Queue…

DataKit之OpenGauss数据迁移工具

# 在讲openGauss和datakit之前&#xff0c;我先说下pgloader这个工具也支持将数据从mysql同步到openGauss或者postgresql&#xff0c;但是 注意了&#xff0c;官网明确说明了不支持视图和触发器的迁移&#xff0c;如果你只是迁移表结构和数据&#xff0c;那么这个既简单又快下面…

使用Go的tls库搭建HTTPS服务

文章目录 tls.go 中文文档使用OpenSSL生成证书Win系统安装openssl生成证书 HTTP情况下的通信编写服务器代码编写客户端代码 tls.go 中文文档 https://studygolang.com/pkgdoc 使用OpenSSL生成证书 Win系统安装openssl 安装地址 https://slproweb.com/products/Win32OpenSSL.…

设计模式17-适配模式

设计模式17-适配模式 动机定义与结构C代码推导总结应用具体应用示例 动机 在软件系统中由于应用环境的变化常常需要将一些现存的对象。放到新的环境中去应用。但是新环境要求的接口是这些现存对象所不满足的。那么这种情况下如何应对这种迁移的变化&#xff1f;如何既能利用现…

计算机毕业设计选题推荐-戏曲文化体验系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

Python自动发送邮件如何设置邮件内容格式?

Python自动发送邮件时&#xff0c;如何自动化发送HTML格式邮件&#xff1f; Python是一种功能强大且灵活的编程语言&#xff0c;广泛用于各种自动化任务&#xff0c;其中包括自动发送邮件。AokSend将介绍在使用Python自动发送邮件时&#xff0c;如何设置邮件内容的格式&#x…

【系统架构设计师】二十二、嵌入式系统架构设计理论与实践②

目录 五、嵌入式中间件 5.1 嵌入式中间件定义 5.2 嵌入式中间件的分类 六、嵌入式系统软件架构设计方法 6.1 基于架构的软件设计开发方法的应用 6.2 属性驱动的软件设计方法 6.2.1 ADD 开发方法的质量属性与场景 6.2.2 ADD 开发过程 6.3 实时系统设计方法 6.3.1 DART…