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

【算法】【动规】乘积为正数的最长子数组长度


跳转汇总链接

👉🔗算法题汇总链接


1.1 乘积为正数的最长子数组长度

🔗题目链接

给你一个整数数组 nums ,请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。

在写代码前,务必先做好这五步!梳理清楚思路,写代码只是顺手的事儿,这是第一道题,所以会详细描述分析方法,后面的题也是同一个流程~

  1. 状态表示
    • 本题得需要两个 dp 表,这里做 f 表和 g 表(设两个表不是一开始就能看出来的,是分析后得出的。先按照题意设一个记录乘积为正数的的最长子数组的长度 f 表,后面在分析正负数情况的时候发现还需要一个记录负数的,于是增添了 g 表)
    • f[i] 表示:以 i 位置元素为结尾乘积为正数的最长子数组的长度
    • g[i] 表示:以 i 位置元素为结尾乘积为负数的最长子数组的长度
  2. 状态转移方程在这里插入图片描述
    • 分析 f:首先将“子数组乘积为正数”中的“子数组”,分为自身和自身+之前的解,按照题意分为长度为1或者长度大于1,可以分析状态转移方程(如下) 在这里插入图片描述
      • 原本需要分成这两类,是因为一般会取 max(自身,自身+之前的解) 或是 min(自身,自身+之前的解),但是这道题我们可以观察到,列出来的方程中 nums[i] 符号相同时的情况可以覆盖另一个,所以方程可以简单写成如下。
        在这里插入图片描述
    • g 表的分析同理。
      在这里插入图片描述
  3. 初始化
    • 涉及到 -1 的位置可能在填表的时候越界,这里选用在表的首部多加一个空格的方式防止越界,初始化内容为 0,不会影响后续表的填写。
  4. 填表顺序
    • 从左往右,两张表一起填。
  5. 返回值
    • 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;}
};

🥰如果本文对你有些帮助,欢迎👉 点赞 收藏 关注,你的支持是对作者大大莫大的鼓励!!(✿◡‿◡) 若有差错恳请留言指正~~


相关文章:

【算法】【动规】乘积为正数的最长子数组长度

跳转汇总链接 &#x1f449;&#x1f517;算法题汇总链接 1.1 乘积为正数的最长子数组长度 &#x1f517;题目链接 给你一个整数数组 nums &#xff0c;请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积…...

Kubernetes实战(十四)-k8s高可用集群扩容master节点

1 单master集群和多master节点集群方案 1.1 单Master集群 k8s 集群是由一组运行 k8s 的节点组成的&#xff0c;节点可以是物理机、虚拟机或者云服务器。k8s 集群中的节点分为两种角色&#xff1a;master 和 node。 master 节点&#xff1a;master 节点负责控制和管理整个集群…...

Spring之容器:IOC(1)

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…...

【.Net 6.0--通用帮助类--ConvertHelper】

前言 类型转换帮助类&#xff0c;包含下表中的方法&#xff1a; 方法名方法解释ObjToIntobject转intObjToMoneyobject转doubleObjToStringobject转stringObjToDecimalobject转decimalObjToDateobject转datetimeObjToDateSplitYMDobject转datetime&#xff08;yyyy-MM-dd&…...

【加解密】报文签名与加解密,MD5,RSA,AES使用案例(基于 Java)

需要考虑哪些问题&#xff1f; 在进行报文传输时&#xff0c;有两个问题需要考虑&#xff1a; 消息防篡改加密报文 定义消息结构 为了方便后面使用&#xff0c;这里定义消息结构&#xff1a; public static class Message {public String data; //消息public String sign;…...

新建vue3项目

三种方法 一. 第一种方式 1、操作步骤&#xff1a; 创建项目目录 vue create 项目名称选择配置方式 ? Please pick a preset: #选择一个配置 Default &#xff08;[Vue 3] babel, eslint&#xff09;Default &#xff08;[Vue 2] babel, eslint&#xff09;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. 需求 各位盆友在日常开发中&#xff0c;有没有遇到上游接口突然不合作了&#xff0c;临时需要切换其他接口的情况&#xff1f;这不巧了&#xff0c;博主团队近期遇到了&#xff0c;又尴尬又忐忑。 尴尬的是临时通知不合作了&#xff0c;事前没有任何提醒&#xff1b; 忐忑…...

PMP项目管理 - 沟通管理

系列文章目录 PMP项目管理 - 质量管理 PMP项目管理 - 采购管理 PMP项目管理 - 资源管理 PMP项目管理 - 风险管理 现在的一切都是为将来的梦想编织翅膀&#xff0c;让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in…...

fckeditor编辑器改造示例:增加PRE,CODE控件

查看专栏目录 Network 灰鸽宝典专栏主要关注服务器的配置&#xff0c;前后端开发环境的配置&#xff0c;编辑器的配置&#xff0c;网络服务的配置&#xff0c;网络命令的应用与配置&#xff0c;windows常见问题的解决等。 文章目录 修改方法&#xff1a;1&#xff09;修改fckco…...

风速预测(五)基于Pytorch的EMD-CNN-LSTM模型

目录 前言 1 风速数据EMD分解与可视化 1.1 导入数据 1.2 EMD分解 2 数据集制作与预处理 2.1 先划分数据集&#xff0c;按照8&#xff1a;2划分训练集和测试集 2.2 设置滑动窗口大小为96&#xff0c;制作数据集 3 基于Pytorch的EMD-CNN-LSTM模型预测 3.1 数据加载&…...

单元测试二(理论)-云计算2023.12-云南农业大学

文章目录 一、单选题1、三次握手、四次挥手发生在网络模型的哪一层上&#xff1f;2、互联网Internet的拓扑结构是什么&#xff1f;3、以下哪一种网络设备是工作在网络层的&#xff1f;4、以下哪种关于分组交换网络的说法是错误的&#xff1f;5、以下哪种协议是在TCP/IP模型中的…...

QModelIndex 是 Qt 框架中的一个类,用于表示数据模型中的索引位置

QModelIndex 是 Qt 框架中的一个类&#xff0c;用于表示数据模型中的索引位置。 在 Qt 中&#xff0c;数据模型是一种组织和管理数据的方式&#xff0c;常见的数据模型包括 QAbstractItemModel、QStandardItemModel 和 QSqlQueryModel 等。QModelIndex 类提供了一种标识数据模…...

前端实现一个时间区间内,再次单选功能,使用Antd组件库内日历组件Calendar

需求&#xff1a;需要先让用户选择一个时间区间&#xff0c;然后再这个时间区间中&#xff0c;让用户再次去单选其种特殊日期。 思路&#xff1a; 1.先用Antd组件库中日期选择DatePicker.RangePicker实现让用户选择时间区间 2.在选择完时间区间后&#xff0c;用这个时间区间…...

【运维笔记】Hyperf正常情况下Xdebug报错死循环解决办法

问题描述 在使用hyperf进行数据库迁移时&#xff0c;迁移报错&#xff1a; 查看报错信息&#xff0c;错误描述是Xdebug检测到死循环&#xff0c;可是打印的堆栈确实正常堆栈&#xff0c;没看到死循环。 寻求解决 gpt 说的跟没说一样。。 google一下 直接把报错信息粘贴上去…...

嵌入式开发中的总线与时钟

总线 AHB总线 AHB的全称是"Advanced High-performance Bus",中文翻译就是"高级高性能总线"。这是一种在计算机系统中用于连接不同硬件组件的总线架构,它可以帮助这些组件之间高效地传输数据和信息。这个总线架构通常用于处理速度较快且对性能要求较高的…...

k8s debug 浅谈

一 k8s debug 浅谈 说明&#xff1a; 本文只是基于对kubectl debug浅显认识总结的知识点,后续实际使用再补充案例 Kubernetes 官方出品调试工具上手指南(无需安装&#xff0c;开箱即用) debug-application 简化 Pod 故障诊断: kubectl-debug 介绍 1.18 版本之前需要自己…...

Day10 Liunx高级系统设计11-数据库2

DQL:数据查询语言 查询全表 select * from 表名; 查询指定列 select 列名 1, 列名 2,… from 表名 ; 条件查询 select * from 表名 where 条件 ; 注意&#xff1a; 条件查询就是在查询时给出 WHERE 子句&#xff0c;在 WHERE 子句中可以使用如下运算符及关键 字&#…...

车载导航系统UI界面,可视化大屏设计(PS源文件)

大屏组件可以让UI设计师的工作更加便捷&#xff0c;使其更高效快速的完成设计任务。现分享车载导航系统科技风蓝黑简约UI界面、车载系统UI主界面、车载系统科技风UI界面、首页车载系统科技感界面界面的大屏Photoshop源文件&#xff0c;开箱即用&#xff01; 若需 更多行业 相关…...

工作之踩坑记录

1.i386架构之atol函数使用导致的业务程序错误&#xff1a; 情景:将框架传递的链接地址采用整形保存传输,在i386架构上导致地址比较大&#xff0c;采用atol转型可能导致数据被截断出现异常。 方案:采用atoll更大的数据类型进行处理即可避免该问题。 2.Json库使用注意long int问…...

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

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

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...