leetcode 152. 乘积最大子数组「贪心」「动态规划」
152. 乘积最大子数组
题目描述:
给你一个整数数组nums,请你找出数组中乘积最大的非空连续子数组,并返回该子数组所对应的乘积
思路1:贪心
由于 n u m s [ i ] nums[i] nums[i]都是整数,所以多乘一些数肯定不会让绝对值变小,所以我们就要尽可能多乘一些数
首先,我们考虑最简单的例子,也就是不包含0的情况:
- 统计负数的数量,如果是偶数,那直接返回所有数的乘积即可
- 如果负数的数量是奇数,我们就考虑删掉一个负数,由于我们上面说过,多乘一些数不会让乘积的绝对值变小,所以我们要尽可能少删数,从左往右找到第一个,下标为id1,从右往左找到第一个,下标为id2,要么是删id1往左的所有数,要么是删id2往右的所有数,两种情况取最大值就行
- 你可能会怀疑,为什么答案不可能是被删除的那一段,因为被删除的那一段都在另一半计算过了,删id1往左的所有数时,这段在计算删id2往右的所有数时,被计算过了
class Solution {
public:int fuck(int l, int r, vector<int>nums){if(l > r || l < 0 || r >= nums.size())return -2e9;if(l == r)return nums[l];int mul = 1;for(int i = l; i <= r; ++i)mul *= (nums[i] > 0 ? 1 : -1);if(mul > 0){for(int i = l; i <= r; ++i)mul *= nums[i];return mul;}mul = -1;int id1 = -1, id2 = -1;for(int i = l; i <= r; ++i){mul *= (nums[i] > 0 ? 1 : -1);if(mul > 0){id1 = i;break;}}int ans1 = 1, ans2 = 1;for(int i = id1 + 1; i <= r; ++i){ans1 *= nums[i];}mul = -1;for(int i = r; i >= l; --i){mul *= (nums[i] > 0 ? 1 : -1);if(mul > 0){id2 = i;break;}}for(int i = id2 - 1; i >= l; --i){ans2 *= nums[i];}return max(ans1, ans2);}int maxProduct(vector<int>& nums) {vector<int>v;for(int i = 0; i < nums.size(); ++i){if(nums[i] == 0)v.push_back(i);}if(v.empty())return fuck(0, nums.size() - 1, nums);int ans = 0;v.push_back(nums.size());int pre = -1;for(int i = 0; i < v.size(); ++i){ans = max(ans, fuck(pre + 1, v[i] - 1, nums));pre = v[i];}return ans;}
};
思路2:DP
这题和最大子数组和的题型有一点像,但是不可以像它那样去进行转移,不能仅仅维护一个最大值,这样会忽略偶数个负数乘起来也是正数的情况,有一种局部贪心的感觉
所以还需要维护一个最小值
-
状态:
- m a x n [ i ] maxn[i] maxn[i]表示以 n u m s [ i ] nums[i] nums[i]结尾的子数组乘积的最大值
- m i n x [ i ] minx[i] minx[i]表示以 n u m s [ i ] nums[i] nums[i]结尾的子数组乘积的最小值
-
转移方程:
-
n u m [ i ] > 0 num[i] > 0 num[i]>0
- m a x n [ i ] = m a x ( n u m s [ i ] , m a x n [ i − 1 ] ∗ n u m s [ i ] ) ; maxn[i] = max(nums[i], maxn[i - 1] * nums[i]); maxn[i]=max(nums[i],maxn[i−1]∗nums[i]);
- m i n x [ i ] = m i n ( m i n x [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; minx[i] = min(minx[i - 1] * nums[i], nums[i]); minx[i]=min(minx[i−1]∗nums[i],nums[i]);
-
n u m [ i ] < 0 num[i] < 0 num[i]<0
- m a x n [ i ] = m a x ( m i n x [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; maxn[i] = max(minx[i - 1] * nums[i], nums[i]); maxn[i]=max(minx[i−1]∗nums[i],nums[i]);
- m i n x [ i ] = m i n ( m a x n [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; minx[i] = min(maxn[i - 1] * nums[i], nums[i]); minx[i]=min(maxn[i−1]∗nums[i],nums[i]);
-
为了解决数据加强的问题,可以用double卡过去
class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<double>maxn(n), minx(n);double ans = nums[0];maxn[0] = minx[0] = nums[0];for(int i = 1; i < n; ++i){if(nums[i] > 0){maxn[i] = max((double)nums[i], maxn[i - 1] * nums[i]);minx[i] = min(minx[i - 1] * nums[i], (double)nums[i]);}else if(nums[i] < 0){maxn[i] = max(minx[i - 1] * nums[i], (double)nums[i]);minx[i] = min(maxn[i - 1] * nums[i], (double)nums[i]);}ans = max(ans, maxn[i]);}return (int)ans;}
};
相关文章:
leetcode 152. 乘积最大子数组「贪心」「动态规划」
152. 乘积最大子数组 题目描述: 给你一个整数数组nums,请你找出数组中乘积最大的非空连续子数组,并返回该子数组所对应的乘积 思路1:贪心 由于 n u m s [ i ] nums[i] nums[i]都是整数,所以多乘一些数肯定不会让绝…...
Android项目目录结构
Android项目目录结构 1. 顶层目录2. 重要的顶层文件和目录3. app模块目录结构4. 重要的**app**模块文件和目录5. 典型的 **build.gradle** 文件内容 典型的Android项目结构的详细介绍。 1. 顶层目录 MyAndroidApp/ ├── .gradle/ ├── .idea/ ├── app/ ├── build/ ├…...
网络安全--计算机网络安全概述
文章目录 网络信息系统安全的目标网络安全的分支举例P2DR模型信息安全模型访问控制的分类多级安全模型 网络信息系统安全的目标 保密性 保证用户信息的保密性,对于非公开的信息,用户无法访问并且无法进行非授权访问,举例子就是:防…...
用requirements.txt配置环境
1. 在anaconda创建环境 创建Python版本为3.8的环境,与yolov5所需的包适配。 2. 在Anaconda Prompt中激活环境 (base) C:\Users\吴伊晴>conda activate yolov5 3. 配置环境 用指定路径中的requirements.txt配置环境。 (yolov5) C:\Users\吴伊晴>pip insta…...
APP渗透-android12夜神模拟器+Burpsuite实现
一、夜神模拟器下载地址:https://www.yeshen.com/ 二、使用openssl转换证书格式 1、首先导出bp证书 2、将cacert.der证书在kali中转换 使用openssl生成pem格式证书,并授予最高权限 openssl x509 -inform der -in cacert.der -out cacert.pem chmod 777 cacert…...
源码扭蛋机开发初探
在软件开发的世界里,创新总是层出不穷。今天,我们将一起探讨一个有趣而富有创意的项目——源码扭蛋机。源码扭蛋机,顾名思义,就是将传统的扭蛋机概念与代码编程相结合,让开发者们在扭动的过程中随机获得各种有趣的、实…...
Patch SCN使用说明---惜分飞
软件说明 该软件是惜分飞(https://www.xifenfei.com)开发,仅用来查看和修改Oracle数据库SCN(System Change Number),主要使用在数据库因为某种原因导致无法正常启动的情况下使用该工具进行解决.特别是Oracle新版本中使用隐含参数,event,orad…...
【微服务架构的守护神】Eureka与服务熔断深度解析
标题:【微服务架构的守护神】Eureka与服务熔断深度解析 在微服务架构中,服务的数量众多,网络请求的复杂性也随之增加,这使得系统的稳定性面临挑战。服务熔断作为一种保护机制,能够在服务出现问题时及时切断请求&#…...
使用label-studio对OCR数据进行预标注
导读 label-studio作为一款数据标注工具相信大家都不陌生,对于需要进行web数据标注协同来说应该是必备工具了,标注的数据类型很全涉及AI的各个任务(图像、语音、NLP、视频等),还支持自定义涉及模版。 然而,我们在标注数据的过程…...
嵌入式linux sqlite3读写demo
以下是一个简单的C语言程序,使用SQLite数据库进行读写操作的示例。请确保您已经安装了SQLite3库。 #include <stdio.h> #include <stdlib.h> #include <sqlite3.h> static int callback(void *NotUsed, int argc, char **argv, char **azColNam…...
vue实现搜索文章关键字,滑到指定位置并且高亮
1、输入搜索条件,点击搜索按钮 2、滑到定位到指定的搜索条件。 <template><div><div class"search_form"><el-inputv-model"searchVal"placeholder"请输入关键字查询"clearablesize"small"style&quo…...
Stable Diffusion与AI艺术:探索人工智能的创造力
引言 随着人工智能(AI)技术的迅猛发展,AI艺术逐渐走进了公众视野。尤其是近年来,Stable Diffusion等技术的出现,显著提升了AI在艺术创作领域的表现力和创造力。这篇文章将深入探讨Stable Diffusion技术的工作原理、应…...
华为HCIP Datacom H12-821 卷26
1.单选题 在VRRP中,同一备份组的设备在进行VRRP报文认证时,以下哪一参数不会影响Master设备和Backup设备认证协商结果 A、认证字 B、优先级 C、认证方式 D、VRRP版本 正确答案: B 解析: 优先级只会影响谁是主谁是备&…...
golang 获取系统的主机 CPU 内存 磁盘等信息
golang 获取系统的主机 CPU 内存 磁盘等信息 要求 需要go1.18或更高版本 官方地址:https://github.com/shirou/gopsutil 使用 #下载包 go get github.com/shirou/gopsutil/v3/cpu go get github.com/shirou/gopsutil/v3/disk go get github.com/shirou/gopsuti…...
Infinitar链游新发展新机遇
区块链游戏市场在近年来经历了显著增长,吸引了大量的投资和关注。随着加密货币和NFT(非同质化代币)概念的普及,越来越多的投资者、游戏开发者和看到了区块链技术在游戏领域的应用潜力,纷纷涌入市场。区块链游戏的用户量…...
Figma 被爆出它剽窃了苹果的设计后撤下了AI工具Make Designs
Figma是一款流行的界面设计工具,最近它推出了一个名为Make Designs的新功能,这个功能利用人工智能帮助用户快速设计应用程序界面。但是,这个工具生成的设计竟然和苹果公司的iOS天气应用非常相似,这让外界怀疑Figma是否剽窃了苹果的…...
ERROR | Web server failed to start. Port 8080 was already in use.
错误提示: *************************** APPLICATION FAILED TO START ***************************Description:Web server failed to start. Port 8080 was already in use.Action:Identify and stop the process thats listening on port 8080 or configure thi…...
C++ 类和对象 构造函数
一 类的6个默认成员函数: 如果一个类中什么成员都没有,简称为空类。 例: #include <iostream> class Empty {// 空类,什么成员都没有 }; 空类中真的什么都没有吗?并不是,任何类在什么都不写时&a…...
纯javascript实现图片批量压缩打包zip下载后端ThinkPHP多国语言切换国际站
最近在做一个多国语言的工具站,需要实现多国语言切换,说到多国语言站,肯定是有2种方式,第一是子域名,第二就是子目录。根据自己的需要来确定。 后台配置如下: 前台显示: 前端纯javascript实现…...
使用ChatGPT写论文,只需四步突破论文写作瓶颈!
欢迎关注,为大家带来最酷最有效的智能AI学术科研写作攻略。关于使用ChatGPT等AI学术科研的相关问题可以和作者七哥(yida985)交流 地表最强大的高级学术AI专业版已经开放,拥有全球领先的GPT学术科研应用,有兴趣的朋友可…...
神领物流项目第一天
文章目录 聚焦快递领域首先第一个是验证码模块流程登录接口权限管家 聚焦快递领域 首先第一个是验证码模块流程 首先生成验证码的流程 可以使用工具类去生成验证码 LineCaptcha lineCaptcha CaptchaUtil.createLineCaptcha(160, 60, 4, 26);// 获取值然后存入redis中 strin…...
[作业]10 枚举-排列类
作业: 已做: #include <iostream> using namespace std; int n; int a[100]; void func(int ,int); int main(){cin>>n;func(0,n);return 0; } void func(int k,int m){if(k>m-1){for(int i0;i<m;i){cout<<a[i];}cout<<en…...
vue2(vue-cli3x[vue.config.js])使用cesium新版(1.117.0)配置过程
看来很多解决方法都没有办法,最后终于。呜呜呜呜 这里我用的是vue-cli去搭建的项目的vue2 项目,其实不建议用vue2搭配cesium。因为目前cesium停止了对vue2的版本更新,现在默认安装都是vue3版本,因此需要控制版本,否则…...
【深度学习】常用命令行指令汇总
这些指令对于管理深度学习环境、监控资源使用、调试程序等方面 查看显卡使用情况 要实时监控NVIDIA显卡的状态,可以使用命令: nvidia-smi -l 1这条命令会每秒刷新一次显卡的使用情况,包括GPU利用率、显存使用情况等。 查看当前Python环境 查看当前使用的Python环境,可…...
谷粒商城学习-11-docker安装redis
文章目录 一,拉取Redis镜像1,搜索Redis的Docker镜像2,拉取Redis镜像3,查看已经拉取的镜像 二,创建、启动Redis容器1,创建redis配置文件2,创建及运行Redis容器3,使用docker ps查看运行…...
C++:类继承是什么,怎么继承
一、类继承是什么 首先了解什么是基类,什么是派生类 在面向对象编程中,基类(Base Class 或 Superclass)是一个类的模板,它定义了一些通用的属性和行为。子类(Derived Class 或 Inheritance)可…...
期权学习必看圣书:《3小时快学期权》要在哪里看?
今天带你了解期权学习必看圣书:《3小时快学期权》要在哪里看?《3小时快学期权》是一本关于股票期权基础知识的书籍。 它旨在通过简明、易懂的语言和实用的案例,让读者在短时间内掌握股票期权的基本概念、操作方法和投资策略。通过这本书&…...
Keepalived 双机热备
1. Keepalived 双机热备 keepalived主要用来提供故障切换(failover)和健康检查(Health Checking)。 1.2 Keepalived 热备方式 Keepalived 采用VRRP (Virtual Router Redundancy Protocol,虚拟路由冗…...
基于React和TypeScript的开源白板项目(Github项目分享)
在学习前端开发的过程中,有时候我们需要一些有趣的项目来提升我们的技能。今天我要给大家介绍的是一个非常酷的项目——NinjaSketch,这是一个用React和TypeScript构建的简易白板工具。这个项目使用了Rough.js来实现手绘风格的效果。尽管这个应用不是响应…...
1019记录
人瑞 - SDK - 外派米哈游 1,接口测试的工具 回答的是postman, 改进:JMeter 2,接口502,什么问题导致的?如何定位? 参考答案:502错误定义:是网关错误, 通俗…...
详细设计与概要设计区别-慧哥充电桩开源系统
概要设计更侧重于系统的整体构架和模块划分,而详细设计则关注具体模块的实现细节。在软件开发过程中,这两个阶段虽然紧密相关,但它们各自有着不同的目标和方法。以下是具体分析: 目标 概要设计:概要设计关注系统整体架…...
vue3 引入百度地图的三种方式
本次也是正好写了一个基于VUE3和百度地图的设计,但奈何第一次使用百度地图,在学习的途中遇到了很多问题,也发现网上的材料相对较少,因此做出了一些小总结,后续还会更新。 一、直接引入 直接在public中的index.html中进…...
鸿蒙开发设备管理:【@ohos.usb (USB管理)】
USB管理 本模块主要提供管理USB设备的相关功能,包括查询USB设备列表、批量数据传输、控制命令传输、权限控制等。 说明: 本模块首批接口从API version 8开始支持。后续版本的新增接口,采用上角标单独标记接口的起始版本。 导入模块 import …...
Golang | Leetcode Golang题解之第204题计数质数
题目: 题解: func countPrimes(n int) int {primes : []int{}isPrime : make([]bool, n)for i : range isPrime {isPrime[i] true}for i : 2; i < n; i {if isPrime[i] {primes append(primes, i)}for _, p : range primes {if i*p > n {break}…...
ELK日志系统和Filebeat采集器的学习总结
ELK是ElasticSerach、Logstash、Kina Logstash负责采集数据,Logstash有三个插件,input、filter、output,filter插件作用是对采集的数据进行处理,过滤的,因此filter插件可以选,可以不用配置。 ElasticSear…...
QML-Grid和OpacityMask
一个格子条,点击缩短 import QtQuick 2.0 import QtQuick.Window 2.12 import QtQuick.Controls 2.5 //导入 import QtGraphicalEffects 1.12Window {id:windowwidth: 600height: 500color: "white"visible: trueGrid {visible: falseid:gridwidth:405he…...
MySQL的并发控制、事务、日志
目录 一.并发控制 1.锁机制 2.加锁与释放锁 二.事务(transactions) 1.事物的概念 2.ACID特性 3.事务隔离级别 三.日志 1.事务日志 2.错误日志 3.通用日志 4.慢查询日志 5.二进制日志 备份 一.并发控制 在 MySQL 中,并发控制是确…...
CNN文献综述
卷积神经网络(Convolutional Neural Networks,简称CNN)是深度学习领域中的一种重要模型,主要用于图像识别和计算机视觉任务。其设计灵感来自于生物学中视觉皮层的工作原理,能够高效地处理图像和语音等数据。 基本原理…...
python语句前面有一个$是什么意思
“$”是汇编语言中的一个预定义符号,等价于当前正汇编到的段的当前偏移值。例如:指令“jmp $3”中的“$”表示当前这条指令在代码段中的偏移量。 代表当前指令的地址,如: data segment str1 db a,b,c,d leng equ $-str 就是当前地…...
wsl安装Linux系统到指定位置
默认情况下,wsl安装的系统,会安装到系统C盘,长期下去,很容易把C盘的空间消耗完,从而影响系统的正常运行,所以我建议是将wsl所有的系统都安装到其它磁盘中,便于维护。 1、导出镜像 通过wsl -l -v 查看当前已安装的系统版本。 导出到当前目录位置,也可以指定目录位置。 w…...
[笔记] 高等数学在各工程门类的典型应用场景
1.应用场景 1.微积分似乎是在解算椭圆方程中引入的?但是这个数学工具第一次应用于现实的工程问题是什么时候?什么场景?什么问题? 微积分的发展确实与椭圆方程有关,但它最初的应用场景远不止于此。 微积分首次被应用…...
刀片服务器和机架式服务器有何区别
刀片服务器和机架式服务器有何区别 一、物理设计: 刀片服务器:刀片服务器是一种相对较轻薄的服务器设计,其物理形状类似于刀片,通常插入到专用的刀片机箱中。每个刀片通常包含一个或多个服务器节点,共享一些基本的资源…...
SQLyog脚本无限试用重置脚本
文章目录 引言脚本(win)必要操作、说明 引言 SQLyog 需要po jie,但是网上的没看到很好使的,直接下的官方。能处理14天试用也是很ok的。 脚本(win) echo offREM SQLyog注册表key,可能跟你的不一样,如果不一样,请替换…...
代码随想录训练营第二十九天 134加油站 135分发糖果 860柠檬水找零 406根据身高重建队列
第一题: 原题链接:134. 加油站 - 力扣(LeetCode) 思路: 需要三个变量,一个变量start记录结果也就是出发的第一个加油站,一个变量curSum来记录此时加油耗油后剩余的油量,如果发现c…...
智能生产管理系统设计
智能生产管理系统的设计旨在提升制造业的效率、灵活性和响应速度,通过集成先进的信息技术(如物联网IoT、大数据分析、人工智能AI、云计算等)实现生产过程的智能化。以下是一些关键设计要素和步骤,用于构建一个高效的智能生产管理系…...
满足GMSL静电防护要求的方案
什么是GMSL?它是做什么用的?它有什么优点?设计GMSL防静电有啥难度? 带着这些疑问我们先了解下什么是GMSL。 一.简述 GMSL GMSL(Gigabit Multimedia Serial Link)即千兆多媒体串行链路…...
【Odoo开源ERP】别把ERP与进销存软件混为一谈
导读:企业使用ERP软件能够实现管理升级,多方信息集成,按照既定策略逻辑运算,生成计划建议,减少人力成本,提高准确率的同时提高经营能力。 ERP,是MRP II的下一代软件,除了MRP II已有的…...
八、浏览器同源策略
上一篇👉: 浏览器垃圾回收机制 文章目录 浏览器同源策略1.同源策略的定义2.同源策略的作用3.同源策略的限制范围4.解决跨域方案汇总1.CORS(跨源资源共享)2.JSONP3.postMessage 跨域4.Nginx代理跨域5.Node.js中间件代理跨域6.document.domain…...
重载赋值运算符
c编译器可能会给类添加四个函数 1默认构造函数 2默认析构函数 3默认拷贝构造函数,对成员变量进行浅拷贝。 4默认赋值函数,队成员变量进行浅拷贝。 #include<iostream> using namespace std; class CGirl { public:int m_bh;string m_name;voi…...
数字信号处理及MATLAB仿真(2)——离散系统
上回书说到如何来编写一些简单的离散时间序列,今天咱们就来谈谈一些关于常系数差分方程的操作吧。 说到这里咱们对于常系数差分方程可能最关心的就是怎么去求解了。 其中最关键的部分就是filter函数,可以用来计算系统在输入信号为x的输出信号y。大家学过…...