当前位置: 首页 > news >正文

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[i1]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[i1]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[i1]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[i1]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. 乘积最大子数组 题目描述&#xff1a; 给你一个整数数组nums&#xff0c;请你找出数组中乘积最大的非空连续子数组&#xff0c;并返回该子数组所对应的乘积 思路1&#xff1a;贪心 由于 n u m s [ i ] nums[i] nums[i]都是整数&#xff0c;所以多乘一些数肯定不会让绝…...

Android项目目录结构

Android项目目录结构 1. 顶层目录2. 重要的顶层文件和目录3. app模块目录结构4. 重要的**app**模块文件和目录5. 典型的 **build.gradle** 文件内容 典型的Android项目结构的详细介绍。 1. 顶层目录 MyAndroidApp/ ├── .gradle/ ├── .idea/ ├── app/ ├── build/ ├…...

网络安全--计算机网络安全概述

文章目录 网络信息系统安全的目标网络安全的分支举例P2DR模型信息安全模型访问控制的分类多级安全模型 网络信息系统安全的目标 保密性 保证用户信息的保密性&#xff0c;对于非公开的信息&#xff0c;用户无法访问并且无法进行非授权访问&#xff0c;举例子就是&#xff1a;防…...

用requirements.txt配置环境

1. 在anaconda创建环境 创建Python版本为3.8的环境&#xff0c;与yolov5所需的包适配。 2. 在Anaconda Prompt中激活环境 (base) C:\Users\吴伊晴>conda activate yolov5 3. 配置环境 用指定路径中的requirements.txt配置环境。 (yolov5) C:\Users\吴伊晴>pip insta…...

APP渗透-android12夜神模拟器+Burpsuite实现

一、夜神模拟器下载地址&#xff1a;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…...

源码扭蛋机开发初探

在软件开发的世界里&#xff0c;创新总是层出不穷。今天&#xff0c;我们将一起探讨一个有趣而富有创意的项目——源码扭蛋机。源码扭蛋机&#xff0c;顾名思义&#xff0c;就是将传统的扭蛋机概念与代码编程相结合&#xff0c;让开发者们在扭动的过程中随机获得各种有趣的、实…...

Patch SCN使用说明---惜分飞

软件说明 该软件是惜分飞&#xff08;https://www.xifenfei.com&#xff09;开发&#xff0c;仅用来查看和修改Oracle数据库SCN(System Change Number),主要使用在数据库因为某种原因导致无法正常启动的情况下使用该工具进行解决.特别是Oracle新版本中使用隐含参数,event,orad…...

【微服务架构的守护神】Eureka与服务熔断深度解析

标题&#xff1a;【微服务架构的守护神】Eureka与服务熔断深度解析 在微服务架构中&#xff0c;服务的数量众多&#xff0c;网络请求的复杂性也随之增加&#xff0c;这使得系统的稳定性面临挑战。服务熔断作为一种保护机制&#xff0c;能够在服务出现问题时及时切断请求&#…...

使用label-studio对OCR数据进行预标注

导读 label-studio作为一款数据标注工具相信大家都不陌生&#xff0c;对于需要进行web数据标注协同来说应该是必备工具了&#xff0c;标注的数据类型很全涉及AI的各个任务(图像、语音、NLP、视频等)&#xff0c;还支持自定义涉及模版。 然而&#xff0c;我们在标注数据的过程…...

嵌入式linux sqlite3读写demo

以下是一个简单的C语言程序&#xff0c;使用SQLite数据库进行读写操作的示例。请确保您已经安装了SQLite3库。 #include <stdio.h> #include <stdlib.h> #include <sqlite3.h> static int callback(void *NotUsed, int argc, char **argv, char **azColNam…...

vue实现搜索文章关键字,滑到指定位置并且高亮

1、输入搜索条件&#xff0c;点击搜索按钮 2、滑到定位到指定的搜索条件。 <template><div><div class"search_form"><el-inputv-model"searchVal"placeholder"请输入关键字查询"clearablesize"small"style&quo…...

Stable Diffusion与AI艺术:探索人工智能的创造力

引言 随着人工智能&#xff08;AI&#xff09;技术的迅猛发展&#xff0c;AI艺术逐渐走进了公众视野。尤其是近年来&#xff0c;Stable Diffusion等技术的出现&#xff0c;显著提升了AI在艺术创作领域的表现力和创造力。这篇文章将深入探讨Stable Diffusion技术的工作原理、应…...

华为HCIP Datacom H12-821 卷26

1.单选题 在VRRP中&#xff0c;同一备份组的设备在进行VRRP报文认证时&#xff0c;以下哪一参数不会影响Master设备和Backup设备认证协商结果 A、认证字 B、优先级 C、认证方式 D、VRRP版本 正确答案&#xff1a; B 解析&#xff1a; 优先级只会影响谁是主谁是备&…...

golang 获取系统的主机 CPU 内存 磁盘等信息

golang 获取系统的主机 CPU 内存 磁盘等信息 要求 需要go1.18或更高版本 官方地址&#xff1a;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链游新发展新机遇

区块链游戏市场在近年来经历了显著增长&#xff0c;吸引了大量的投资和关注。随着加密货币和NFT&#xff08;非同质化代币&#xff09;概念的普及&#xff0c;越来越多的投资者、游戏开发者和看到了区块链技术在游戏领域的应用潜力&#xff0c;纷纷涌入市场。区块链游戏的用户量…...

Figma 被爆出它剽窃了苹果的设计后撤下了AI工具Make Designs

Figma是一款流行的界面设计工具&#xff0c;最近它推出了一个名为Make Designs的新功能&#xff0c;这个功能利用人工智能帮助用户快速设计应用程序界面。但是&#xff0c;这个工具生成的设计竟然和苹果公司的iOS天气应用非常相似&#xff0c;这让外界怀疑Figma是否剽窃了苹果的…...

ERROR | Web server failed to start. Port 8080 was already in use.

错误提示&#xff1a; *************************** 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个默认成员函数&#xff1a; 如果一个类中什么成员都没有&#xff0c;简称为空类。 例&#xff1a; #include <iostream> class Empty {// 空类&#xff0c;什么成员都没有 }; 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任何类在什么都不写时&a…...

纯javascript实现图片批量压缩打包zip下载后端ThinkPHP多国语言切换国际站

最近在做一个多国语言的工具站&#xff0c;需要实现多国语言切换&#xff0c;说到多国语言站&#xff0c;肯定是有2种方式&#xff0c;第一是子域名&#xff0c;第二就是子目录。根据自己的需要来确定。 后台配置如下&#xff1a; 前台显示&#xff1a; 前端纯javascript实现…...

使用ChatGPT写论文,只需四步突破论文写作瓶颈!

欢迎关注&#xff0c;为大家带来最酷最有效的智能AI学术科研写作攻略。关于使用ChatGPT等AI学术科研的相关问题可以和作者七哥&#xff08;yida985&#xff09;交流 地表最强大的高级学术AI专业版已经开放&#xff0c;拥有全球领先的GPT学术科研应用&#xff0c;有兴趣的朋友可…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...