LeetCode hot100-88

https://leetcode.cn/problems/maximum-product-subarray/?envType=study-plan-v2&envId=top-100-liked

152. 乘积最大子数组
已解答
中等
相关标签
相关企业
给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续 
子数组
(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。

为了求得最大乘积,我们可以采用动态规划的思路。具体来说,我们需要维护两个变量:

max_so_far:当前遍历到的位置的最大乘积。
min_so_far:当前遍历到的位置的最小乘积(因为负数乘以负数可能变成正数)。
主要思想:
如果遇到正数,max_so_far 会乘以该数来增大乘积,min_so_far 会乘以该数来减少乘积。
如果遇到负数,max_so_far 会和 min_so_far 交换,因为负数与最小值相乘可能变成最大值,min_so_far 会乘以负数变得更加负。
如果遇到零,乘积会变成零,此时我们需要重置 max_so_far 和 min_so_far。

public class Solution {public int maxProduct(int[] nums) {// 初始化最大值和最小值int max_so_far = nums[0];int min_so_far = nums[0];int result = nums[0];// 从第二个元素开始遍历数组for (int i = 1; i < nums.length; i++) {// 如果当前元素是负数,交换最大值和最小值if (nums[i] < 0) {int temp = max_so_far;max_so_far = min_so_far;min_so_far = temp;}// 更新最大值和最小值max_so_far = Math.max(nums[i], max_so_far * nums[i]);min_so_far = Math.min(nums[i], min_so_far * nums[i]);// 更新结果result = Math.max(result, max_so_far);}return result;}
}

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

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

相关文章

pdf文件中的表格无损提取方案(pdf转Excel),非OCR

非OCR方案&#xff0c;基于java&#xff1a; aspose 21.11版本&#xff08;网上有破解方法&#xff0c;或者参考我另外一篇文章&#xff09; 转换pdf&#xff08;含表格&#xff09;为excel文件&#xff0c;然后可以使用poi对得到的excel文件进行微调。 但是上述方案&#x…

第十七章:反射+设计模式

一、反射 1. 反射(Reflection)&#xff1a;允许在程序运行状态中&#xff0c;可以获取任意类中的属性和方法&#xff0c;并且可以操作任意对象内部的属 性和方法&#xff0c;这种动态获取类的信息及动态操作对象的属性和方法对应的机制称为反射机制。 2. 类对象 和 类的对象(实…

【Linux】结构化命令:for命令

1、基本介绍 for循环假定各个值之间是以空格、制表符或换行符分隔的&#xff0c;因为特殊的环境变量IFS&#xff08;internal field separator&#xff0c;内部字段分隔符&#xff09;&#xff0c;默认情况下&#xff0c;它会将这三者视为字段分隔符。 格式&#xff1a; for v…

Nginx(Linux之Ubuntu)

1.1.什么是Nginx Nginx&#xff08;发音为"engine x"&#xff09;是由俄罗斯开发者Igor Sysoev创建的一款轻量级、高性能的Web服务器。它首次发布于2004年&#xff0c;如今已成为全球最受欢迎的Web服务器之一。Nginx以其卓越的性能和灵活性而闻名&#xff0c;适用于…

vue3+TS+vueX的记录

要求&#xff1a;在页面中使用输入框输入回车后将数据保存到vuex中的数组list中 list为一个数组 内部三个属性为 id value status id为时间戳 value为string 输入的字符串 status为定义的三种状态 待办 在办 完成 1、创建仓库 将 仓库拆分 import { createStore } fro…

【图像分类实用脚本】数据可视化以及高数量类别截断

图像分类时&#xff0c;如果某个类别或者某些类别的数量远大于其他类别的话&#xff0c;模型在计算的时候&#xff0c;更倾向于拟合数量更多的类别&#xff1b;因此&#xff0c;观察类别数量以及对数据量多的类别进行截断是很有必要的。 1.准备数据 数据的格式为图像分类数据集…

Javascript-web API-day02

文章目录 01-事件监听02-点击关闭广告03-随机点名案例04-鼠标经过或离开事件05-可点击的轮播图06-小米搜索框07-键盘类型事件08-键盘事件-发布评论案例09-focus选择器10-评论回车发布11-事件对象12-trim方法13-环境对象14-回调函数15-tab栏切换 01-事件监听 <!DOCTYPE html…

c语言-------循环结构

基本概念 循环结构是C语言中一种重要的程序控制结构&#xff0c;它允许程序在满足一定条件的情况下&#xff0c;反复执行一段代码。这可以避免重复编写相似的代码&#xff0c;提高代码的效率和可读性。 while循环 语法格式 while (条件表达式) { 循环体语句; } 执行流程 首先判…

Centos创建共享文件夹拉取文件

1.打开VMware程序&#xff0c;鼠标右检你的虚拟机&#xff0c;打开设置 2.点击选项——共享文件夹——总是启用 点击添加&#xff0c;设置你想要共享的文件夹在pc上的路径&#xff08;我这里已经添加过了就不加了&#xff09; 注意不要中文&#xff0c;建议用share&#xff0c…

SpringBoot项目Jar包使用systemctl运行

1. 前言 SpringBoot项目打成jar包后&#xff0c;可以直接使用 java -jar xxx.jar 启动。但是为了方便启动和停止服务&#xff0c;通常我们会写两个脚本&#xff0c;分别是启动脚本 start.sh 和 停止脚本 shutdown.sh&#xff08;这两个脚本内容我们下文会实现&#xff09;&…

计算机网络-L2TP VPN基础概念与原理

一、概述 前面学习了GRE和IPSec VPN&#xff0c;今天继续学习另外一个也很常见的VPN类型-L2TP VPN。 L2TP&#xff08;Layer 2 Tunneling Protocol&#xff09; 协议结合了L2F协议和PPTP协议的优点&#xff0c;是IETF有关二层隧道协议的工业标准。L2TP是虚拟私有拨号网VPDN&…

踩准智能汽车+机器人两大风口,速腾聚创AI+机器人应用双线爆发

日前&#xff0c;RoboSense速腾聚创交出了一份亮眼的Q3财报。受到多重利好消息影响&#xff0c;其股价也应势连续大涨。截止12月9日发稿前&#xff0c;速腾聚创股价近一个月内累计涨幅已超88%。 财务数据方面&#xff0c;速腾聚创在今年前三季度实现总收入约11.3亿元&#xff0…

使用Idea自带的git功能进行分支合并

文章目录 1.背景描述2.分支切换3.分支合并的具体操作4.将在local环境下&#xff0c;从dev合并到qas分支上的代码&#xff0c;推送到远端 1.背景描述 目前在开发的当前项目有四个分支&#xff0c;master(主分支)、pre(预生产分支)、qas(测试分支)、dev(开发分支)&#xff1b; …

EE308FZ_Sixth Assignment_Beta Sprint_Sprint Essay 3

Assignment 6Beta SprintCourseEE308FZ[A] — Software EngineeringClass Link2401_MU_SE_FZURequirementsTeamwork—Beta SprintTeam NameFZUGOObjectiveSprint Essay 3_Day5-Day6 (12.15-12.16)Other Reference1. WeChat Mini Program Design Guide 2. Javascript Style Guid…

凯酷全科技抖音电商服务的卓越践行者

在数字经济蓬勃发展的今天&#xff0c;电子商务已成为企业增长的新引擎。随着短视频平台的崛起&#xff0c;抖音作为全球领先的短视频社交平台&#xff0c;不仅改变了人们的娱乐方式&#xff0c;也为品牌和商家提供了全新的营销渠道。厦门凯酷全科技有限公司&#xff08;以下简…

架构信息收集(小迪网络安全笔记~

附&#xff1a;完整笔记目录~ ps&#xff1a;本人小白&#xff0c;笔记均在个人理解基础上整理&#xff0c;若有错误欢迎指正&#xff01; 2.2 架构信息收集 引子&#xff1a;一个Web应用的构成&#xff0c;由诸多组件&服务相结合&#xff0c;而域名仅是处于Web架构中最表…

一.photoshop导入到spine

这里使用的是 photoshoptospine脚本 下载地址:https://download.csdn.net/download/boyxgb/90156744 脚本的使用,可以通过文件的脚本的浏览,浏览该脚本使用该脚本,也可以将该脚本放在photoshop安装文件夹里的script文件夹下,具体路径:Photoshop\Presets\Scripts,重启photosho…

Mapbox-GL 的源码解读的一般步骤

Mapbox-GL 是一个非常优秀的二三维地理引擎&#xff0c;随着智能驾驶时代的到来&#xff0c;应用也会越来越广泛&#xff0c;关于mapbox-gl和其他地理引擎的详细对比&#xff08;比如CesiumJS&#xff09;&#xff0c;后续有时间会加更。地理首先理解 Mapbox-GL 的源码是一项复…

SparkSQL运行架构及原理

文章目录 SparkSQL运行架构及原理1.1. Catalyst优化器简介1.2. SparkSQL运行架构1.3. SparkSQL解析Core底层原理1.4. 执行计划查看 SparkSQL运行架构及原理 1.1. Catalyst优化器简介 SparkSQL使得我们开发人员可以使用DSL风格的数据来处理数据&#xff0c;甚至可以直接使用SQ…

大数据-254 离线数仓 - Airflow 任务调度 核心交易调度任务集成

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; Java篇开始了&#xff01; 目前开始更新 MyBatis&#xff0c;一起深入浅出&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff0…