【算法】【动规】乘积为正数的最长子数组长度
跳转汇总链接
👉🔗算法题汇总链接
1.1 乘积为正数的最长子数组长度
🔗题目链接
给你一个整数数组 nums ,请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
在写代码前,务必先做好这五步!梳理清楚思路,写代码只是顺手的事儿,这是第一道题,所以会详细描述分析方法,后面的题也是同一个流程~
- 状态表示:
- 本题得需要两个 dp 表,这里做 f 表和 g 表(设两个表不是一开始就能看出来的,是分析后得出的。先按照题意设一个记录乘积为正数的的最长子数组的长度 f 表,后面在分析正负数情况的时候发现还需要一个记录负数的,于是增添了 g 表)
- f[i] 表示:以 i 位置元素为结尾乘积为正数的最长子数组的长度
- g[i] 表示:以 i 位置元素为结尾乘积为负数的最长子数组的长度
- 状态转移方程:
- 分析 f:首先将“子数组乘积为正数”中的“子数组”,分为自身和自身+之前的解,按照题意分为长度为1或者长度大于1,可以分析状态转移方程(如下)
- 原本需要分成这两类,是因为一般会取 max(自身,自身+之前的解) 或是 min(自身,自身+之前的解),但是这道题我们可以观察到,列出来的方程中 nums[i] 符号相同时的情况可以覆盖另一个,所以方程可以简单写成如下。

- 原本需要分成这两类,是因为一般会取 max(自身,自身+之前的解) 或是 min(自身,自身+之前的解),但是这道题我们可以观察到,列出来的方程中 nums[i] 符号相同时的情况可以覆盖另一个,所以方程可以简单写成如下。
- g 表的分析同理。

- 分析 f:首先将“子数组乘积为正数”中的“子数组”,分为自身和自身+之前的解,按照题意分为长度为1或者长度大于1,可以分析状态转移方程(如下)
- 初始化:
- 涉及到 -1 的位置可能在填表的时候越界,这里选用在表的首部多加一个空格的方式防止越界,初始化内容为 0,不会影响后续表的填写。
- 填表顺序:
- 从左往右,两张表一起填。
- 返回值:
- f 表里的最大值。
🐎代码如下:
class Solution {
public:int getMaxLen(vector<int>& nums) {// 1. 创建 dp 表int n = nums.size();vector<int> f(n + 1); // 乘积为正数的最长数auto g = f; // 乘积为负数的最长数// 2. 初始化int fmax = 0;f[0] = g[0] = 0;// 3. 誊写状态转移方式for(int i = 1; i < n + 1; i++){if(nums[i - 1] > 0){f[i] = f[i-1] + 1;g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;}else if(nums[i - 1] < 0){f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;g[i] = f[i-1] + 1;}fmax = max(fmax, f[i]);}// 4. 返回值return fmax;}
};
🥰如果本文对你有些帮助,欢迎👉 点赞 收藏 关注,你的支持是对作者大大莫大的鼓励!!(✿◡‿◡) 若有差错恳请留言指正~~
相关文章:
【算法】【动规】乘积为正数的最长子数组长度
跳转汇总链接 👉🔗算法题汇总链接 1.1 乘积为正数的最长子数组长度 🔗题目链接 给你一个整数数组 nums ,请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积…...
Kubernetes实战(十四)-k8s高可用集群扩容master节点
1 单master集群和多master节点集群方案 1.1 单Master集群 k8s 集群是由一组运行 k8s 的节点组成的,节点可以是物理机、虚拟机或者云服务器。k8s 集群中的节点分为两种角色:master 和 node。 master 节点:master 节点负责控制和管理整个集群…...
Spring之容器:IOC(1)
学习的最大理由是想摆脱平庸,早一天就多一份人生的精彩;迟一天就多一天平庸的困扰。各位小伙伴,如果您: 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持,想组团高效学习… 想写博客但无从下手,急需…...
【.Net 6.0--通用帮助类--ConvertHelper】
前言 类型转换帮助类,包含下表中的方法: 方法名方法解释ObjToIntobject转intObjToMoneyobject转doubleObjToStringobject转stringObjToDecimalobject转decimalObjToDateobject转datetimeObjToDateSplitYMDobject转datetime(yyyy-MM-dd&…...
【加解密】报文签名与加解密,MD5,RSA,AES使用案例(基于 Java)
需要考虑哪些问题? 在进行报文传输时,有两个问题需要考虑: 消息防篡改加密报文 定义消息结构 为了方便后面使用,这里定义消息结构: public static class Message {public String data; //消息public String sign;…...
新建vue3项目
三种方法 一. 第一种方式 1、操作步骤: 创建项目目录 vue create 项目名称选择配置方式 ? Please pick a preset: #选择一个配置 Default ([Vue 3] babel, eslint)Default ([Vue 2] babel, eslint)Manually select …...
出现 Error:Unable to access jarfile xxxx\target\nacos-server.jar 解决方法
目录 1. 问题所示2. 原理分析3. 解决方法1. 问题所示 执行Nacos中的startup.cmd的时候出现闪退,于是在该脚本的最后一行添加pause,查看因为什么原因闪退 出现的bug如下所示:Error:Unable to access jarfile xxxx\target\nacos-server.jar 截图如下所示: 查看内部文件夹,…...
记录一次API报文替换点滴
1. 需求 各位盆友在日常开发中,有没有遇到上游接口突然不合作了,临时需要切换其他接口的情况?这不巧了,博主团队近期遇到了,又尴尬又忐忑。 尴尬的是临时通知不合作了,事前没有任何提醒; 忐忑…...
PMP项目管理 - 沟通管理
系列文章目录 PMP项目管理 - 质量管理 PMP项目管理 - 采购管理 PMP项目管理 - 资源管理 PMP项目管理 - 风险管理 现在的一切都是为将来的梦想编织翅膀,让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in…...
fckeditor编辑器改造示例:增加PRE,CODE控件
查看专栏目录 Network 灰鸽宝典专栏主要关注服务器的配置,前后端开发环境的配置,编辑器的配置,网络服务的配置,网络命令的应用与配置,windows常见问题的解决等。 文章目录 修改方法:1)修改fckco…...
风速预测(五)基于Pytorch的EMD-CNN-LSTM模型
目录 前言 1 风速数据EMD分解与可视化 1.1 导入数据 1.2 EMD分解 2 数据集制作与预处理 2.1 先划分数据集,按照8:2划分训练集和测试集 2.2 设置滑动窗口大小为96,制作数据集 3 基于Pytorch的EMD-CNN-LSTM模型预测 3.1 数据加载&…...
单元测试二(理论)-云计算2023.12-云南农业大学
文章目录 一、单选题1、三次握手、四次挥手发生在网络模型的哪一层上?2、互联网Internet的拓扑结构是什么?3、以下哪一种网络设备是工作在网络层的?4、以下哪种关于分组交换网络的说法是错误的?5、以下哪种协议是在TCP/IP模型中的…...
QModelIndex 是 Qt 框架中的一个类,用于表示数据模型中的索引位置
QModelIndex 是 Qt 框架中的一个类,用于表示数据模型中的索引位置。 在 Qt 中,数据模型是一种组织和管理数据的方式,常见的数据模型包括 QAbstractItemModel、QStandardItemModel 和 QSqlQueryModel 等。QModelIndex 类提供了一种标识数据模…...
前端实现一个时间区间内,再次单选功能,使用Antd组件库内日历组件Calendar
需求:需要先让用户选择一个时间区间,然后再这个时间区间中,让用户再次去单选其种特殊日期。 思路: 1.先用Antd组件库中日期选择DatePicker.RangePicker实现让用户选择时间区间 2.在选择完时间区间后,用这个时间区间…...
【运维笔记】Hyperf正常情况下Xdebug报错死循环解决办法
问题描述 在使用hyperf进行数据库迁移时,迁移报错: 查看报错信息,错误描述是Xdebug检测到死循环,可是打印的堆栈确实正常堆栈,没看到死循环。 寻求解决 gpt 说的跟没说一样。。 google一下 直接把报错信息粘贴上去…...
嵌入式开发中的总线与时钟
总线 AHB总线 AHB的全称是"Advanced High-performance Bus",中文翻译就是"高级高性能总线"。这是一种在计算机系统中用于连接不同硬件组件的总线架构,它可以帮助这些组件之间高效地传输数据和信息。这个总线架构通常用于处理速度较快且对性能要求较高的…...
k8s debug 浅谈
一 k8s debug 浅谈 说明: 本文只是基于对kubectl debug浅显认识总结的知识点,后续实际使用再补充案例 Kubernetes 官方出品调试工具上手指南(无需安装,开箱即用) debug-application 简化 Pod 故障诊断: kubectl-debug 介绍 1.18 版本之前需要自己…...
Day10 Liunx高级系统设计11-数据库2
DQL:数据查询语言 查询全表 select * from 表名; 查询指定列 select 列名 1, 列名 2,… from 表名 ; 条件查询 select * from 表名 where 条件 ; 注意: 条件查询就是在查询时给出 WHERE 子句,在 WHERE 子句中可以使用如下运算符及关键 字&#…...
车载导航系统UI界面,可视化大屏设计(PS源文件)
大屏组件可以让UI设计师的工作更加便捷,使其更高效快速的完成设计任务。现分享车载导航系统科技风蓝黑简约UI界面、车载系统UI主界面、车载系统科技风UI界面、首页车载系统科技感界面界面的大屏Photoshop源文件,开箱即用! 若需 更多行业 相关…...
工作之踩坑记录
1.i386架构之atol函数使用导致的业务程序错误: 情景:将框架传递的链接地址采用整形保存传输,在i386架构上导致地址比较大,采用atol转型可能导致数据被截断出现异常。 方案:采用atoll更大的数据类型进行处理即可避免该问题。 2.Json库使用注意long int问…...
数据库课程设计案例:基于深度感知的智能仓储管理系统
数据库课程设计案例:基于深度感知的智能仓储管理系统 每次路过大型物流仓库,看到那些高耸的货架和穿梭的叉车,我总会想,他们是怎么知道哪个货位是满的,哪个是空的?靠人工盘点?那得累死。靠传统…...
OpenClaw+百川2-13B:个人知识库自动整理与问答系统搭建
OpenClaw百川2-13B:个人知识库自动整理与问答系统搭建 1. 为什么需要本地化知识管理系统 去年整理博士论文资料时,我遇到了一个典型的研究者困境:电脑里堆积了237个PDF、643篇网页存档和无数零散的笔记片段,但需要引用某个概念时…...
OpenClaw备份策略:GLM-4.7-Flash智能管理本地与云端存储
OpenClaw备份策略:GLM-4.7-Flash智能管理本地与云端存储 1. 为什么需要智能备份方案 上周我的移动硬盘突然罢工,导致三个月的项目文档全部丢失。这次惨痛经历让我意识到:传统备份方式已经无法满足现代工作需求。手动备份不仅耗时耗力&#…...
项目管理工具怎么选?8款主流产品测评与选型建议
项目管理工具怎么选?真正需要比较的,不只是功能多少,而是它是否适合团队的协作方式、项目复杂度和管理阶段。本文围绕场景匹配、流程灵活性、信息沉淀、管理视图和落地成本,对8款主流项目管理工具做一轮顾问式测评。引言很多企业在…...
终极指南:用EdgeRemover快速彻底卸载微软Edge浏览器
终极指南:用EdgeRemover快速彻底卸载微软Edge浏览器 【免费下载链接】EdgeRemover PowerShell script to remove Microsoft Edge in a non-forceful manner. 项目地址: https://gitcode.com/gh_mirrors/ed/EdgeRemover 还在为Windows系统中无法彻底移除Micro…...
从Flask裸奔到MCP标准落地:7步迁移指南+自动转换脚本(已验证支撑日均50万次Agent调用)
第一章:Python MCP 服务器开发模板概览与核心价值Python MCP(Model-Controller-Protocol)服务器开发模板是一套面向协议驱动微服务架构的轻量级开发框架,专为快速构建符合 MCP 规范的 AI 工具集成后端而设计。它抽象了协议适配、会…...
深蓝词库转换:如何实现20+输入法词库的一键互通
深蓝词库转换:如何实现20输入法词库的一键互通 【免费下载链接】imewlconverter ”深蓝词库转换“ 一款开源免费的输入法词库转换程序 项目地址: https://gitcode.com/gh_mirrors/im/imewlconverter 你是否曾因更换输入法而不得不放弃多年积累的个人词库&…...
3步深度配置Obsidian Copilot:打造专属AI知识工作流
3步深度配置Obsidian Copilot:打造专属AI知识工作流 【免费下载链接】obsidian-copilot A ChatGPT Copilot in Obsidian 项目地址: https://gitcode.com/gh_mirrors/ob/obsidian-copilot 在信息爆炸时代,知识工作者面临的最大挑战不是获取信息&am…...
NaViL-9B效果实测:支持中英文混排表格图像的行列结构识别与内容提取
NaViL-9B效果实测:支持中英文混排表格图像的行列结构识别与内容提取 1. 模型介绍 NaViL-9B是新一代原生多模态大语言模型,专为处理复杂视觉-语言任务设计。与常规视觉模型不同,它不仅能够理解图片内容,还能精准解析表格、文档等…...
FreeRTOS+LwIP 2.2.0实战:手把手教你理解tcpip_thread的消息处理机制
FreeRTOSLwIP 2.2.0实战:深入解析tcpip_thread的消息驱动架构 在嵌入式网络开发中,理解协议栈的线程模型是构建稳定系统的关键。当FreeRTOS遇上LwIP,tcpip_thread就像一位不知疲倦的邮差,日夜处理着来自各方的网络报文。本文将带您…...
