动态规划-子数组系列——1567.乘积为正数的最长子数组
1.题目解析
题目来源:1567.乘积为正数的最长子数组——力扣

测试用例

2.算法原理
1.状态表示
因为数组中存在正数与负数,如果求乘积为正数的最长子数组,那么存在两种情况使得乘积为正数,第一种就是正数乘以正数,第二种就是负数乘以负数,那么就必须使用两个表来分别存储这两种情况,其中f表存储乘积为正数的子数组最长长度,g表存储乘积为负数的子数组最长长度
f[i]:以第i个位置为结尾的乘积为正数的子数组最长长度
g[i]:以第i个位置为结尾的乘积为负数的子数组最长长度
2.状态转移方程
当遇到的为正数,此时填两个表需要分别用到自己表的前一个位置的值,也就是
f[i]=f[i-1]+1;g[i]=g[i-1]==0?0:g[i-1]+1;这里特殊处理g表是因为当第i个位置之前乘积全为正数时g[i-1]=0,如果此时直接g[i]=g[i-1]+1则不符合实际情况
当遇到的为负数,此时填两个表需要用到对方表内的前一个位置的值,也就是
f[i]=g[i-1]==0?0:g[i-1]+1;g[i]=f[i-1]+1;这里以及特殊处理g[i-1]避免错误
3.初始化
由于填表需要用到前一个位置的值,所以可以开辟一个虚拟位置在循环内初始化两个表,此时需要处理虚拟位置的值,我们由状态转移方程可知在初始化第一个位置时用虚拟位置的值,此时虚拟位置的值为0不会影响结果,所以将虚拟位置置为0即可
4.填表顺序
从左到右,两个表一起填写
5.返回值
返回f表的最大值即可

3.实战代码
class Solution {
public:int getMaxLen(vector<int>& nums) {int n = nums.size();vector<int> f(n+1);vector<int> g(n+1);int ret = INT_MIN;for(int i = 1;i <= n;i++){if(nums[i-1] > 0){f[i] = f[i-1] + 1;g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;}if(nums[i-1] < 0){f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;g[i] = f[i-1] + 1;}ret = max(f[i],ret);} return ret;}
};相关文章:
动态规划-子数组系列——1567.乘积为正数的最长子数组
1.题目解析 题目来源:1567.乘积为正数的最长子数组——力扣 测试用例 2.算法原理 1.状态表示 因为数组中存在正数与负数,如果求乘积为正数的最长子数组,那么存在两种情况使得乘积为正数,第一种就是正数乘以正数,第…...
Linux 运行执行文件并将日志输出保存到文本文件中
在 Linux 系统中运行可执行文件并将日志输出保存到文本文件中,可以使用以下几种方法: 方法一:使用重定向符号 > 或 >> 覆盖写入(>): ./your_executable > logfile.txt这会将可执行文件的输…...
注册安全分析报告:北外网校
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞…...
预警期刊命运逆袭到毕业好刊,仅45天!闭眼冲速度,发文量暴增!
选刊发表不迷路,就找科检易学术 期刊官网:Sustainability | An Open Access Journal from MDPI 1、期刊信息 期刊简介: Sustainability 是一本国际性的、同行评审的开放获取期刊,由MDPI出版社每半月在线出版。该期刊专注于人类…...
【LeetCode每日一题】——523.连续的子数组和
文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 前缀和 二【题目难度】 中等 三【题目编号】 523.连续的子数组和 四【题目描述】 给你一个…...
leetcode54:螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1: 输入:matrix [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5]示例 2: 输入:matrix [[1,2,3,…...
全方面熟悉Maven项目管理工具(三)认识mvn的各类构建命令并创建、打包Web工程
1. POM(核心概念) 1.1 含义 POM: Project Object Model,项目对象模型。 DOM: Document Object Model,文档对象模型,和 POM 类似 它们都是模型化思想的具体体现 1.2 模型化思想 POM 表示将…...
MySQL中查询语句的执行流程
文章目录 前言流程图概述最后 前言 你好,我是醉墨居士,今天我们一起探讨一下执行一条查询的SQL语句在MySQL内部都发生了什么,让你对MySQL内部的架构具备一个宏观上的了解 流程图 概述 对于查询语句的SQL的执行流程,主要可以分为…...
【代码随想录Day47】单调栈Part02
42. 接雨水 题目链接/文章讲解:代码随想录 视频讲解:单调栈,经典来袭!LeetCode:42.接雨水_哔哩哔哩_bilibili 思路概述 问题理解:我们需要计算在给定柱子高度之间可以接住的雨水总量。雨水的量取决于柱子的高度和它们…...
Java全栈经典面试题剖析3】JavaSE面向对象2
目录 面试题2.12 Overload和Override的区别 面试题2.13 Overload方法是否可以改变返回值的类型? 面试题2.14 为什么方法不能根据返回类型来区分重载? 面试题2.15 构造器可不可以被重载或重写? 面试题2.16 在 Java 中定义⼀个不做事且没有…...
@JsonIgnoreProperties做接口对接时使用带来的好处
最近看到有个同事,在代码里面加了JsonIgnoreProperties这个注解,以前还真没有经常去用过,接口对接尤其是跟金蝶、用友等第三方,这个注解在接收数据是非常好用的;接下来带大家一起了解下具体的特性和使用方式 JsonIgno…...
SpringBoot整合mybatisPlus实现批量插入并获取ID
背景:需要实现批量插入并且得到插入后的ID。 使用for循环进行insert这里就不说了,在海量数据下其性能是最慢的。数据量小的情况下,没什么区别。 【1】saveBatch(一万条数据总耗时:2478ms) mybatisplus扩展包提供的:…...
实战RAG第一天——llama_index向量索引,查询引擎,搜索知识库问答,全部代码,保姆级教学
一、llama_index简介 llama_index(以前称为 GPT Index)是一个用于构建、查询、索引大型文档和数据集的开源框架。它的核心功能是帮助开发者将大语言模型(LLM)与自己的数据集无缝集成,从而进行知识库的构建、查询等任务。llama_index 使用 Python 编写,并结合了多种大语言…...
大数据治理
大数据治理是指对大数据的管理和控制,以确保数据的质量、可用性、安全性和合规性。随着大数据技术的不断发展,企业和组织面临着越来越多的数据管理挑战,如数据质量问题、数据安全问题、数据合规问题等。大数据治理成为了企业和组织应对这些挑战的重要手段。 一、大数据治理…...
云计算作业
关闭防火墙 停用Linux 挂载 下载nginx程序 启动nginx程序 连接网卡配置文件并且修改 更改模式为静态手动,并且分别修改ip地址,网关地址,dns 激活 创建自定义文件 定义server模块 监听地址 设置目录 匹配 激活网址根目录 创建目录文…...
复制文件到U盘提示:对于目标文件系统,文件过大
查看U盘属性的文件系统是否为FAT32,需将其改为NTFS 方法一 Win R 输入cmd打开命令行,输入以下命令(注:f为U盘盘符) convert f: /fs:ntfs /x方法二 格式化U盘,右键点击U盘进行格式化,文件系…...
SpringBoot+Swagger2.7.0实现汉化(2.8.0不行)
场景 SpringBootSwagger2实现可视化API文档流程: SpringBootSwagger2实现可视化API文档流程_swagger 可视化端口-CSDN博客 上面SpringBoot中使用swagger的效果 上面使用的是swagger2.8.0,且在线API是英文的。现在要将其进行汉化。 汉化效果 实现 首先打开sprin…...
c++ 散列表
散列表(Hash Table)是一种高效的数据结构,广泛用于实现快速的键值对存储。 基本概念 散列表使用哈希函数将键映射到数组的索引。其主要优点在于平均情况下提供常数时间复杂度的查找、插入和删除操作。 哈希函数: 将键映射到一个固定大小的…...
Windows通过netsh控制安全中心防火墙和网络保护策略
Windows通过netsh控制安全中心防火墙和网络保护策略 1. 工具简介 【1】. Windows安全中心 【2】. netsh工具 netsh(Network Shell) 是一个Windows系统本身提供的功能强大的网络配置命令行工具。 2. 开启/关闭防火墙策略 在设置端口(禁用/启用)前&am…...
UML(Unified Modeling Language,统一建模语言)
UML(Unified Modeling Language,统一建模语言)是一种标准化的图形化语言,用于软件工程中的可视化建模。UML由Grady Booch、James Rumbaugh和Ivar Jacobson共同开发,他们各自的工作(Booch方法、OMT方法和OOS…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
