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

动态规划-子数组系列——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.题目解析 题目来源&#xff1a;1567.乘积为正数的最长子数组——力扣 测试用例 2.算法原理 1.状态表示 因为数组中存在正数与负数&#xff0c;如果求乘积为正数的最长子数组&#xff0c;那么存在两种情况使得乘积为正数&#xff0c;第一种就是正数乘以正数&#xff0c;第…...

Linux 运行执行文件并将日志输出保存到文本文件中

在 Linux 系统中运行可执行文件并将日志输出保存到文本文件中&#xff0c;可以使用以下几种方法&#xff1a; 方法一&#xff1a;使用重定向符号 > 或 >> 覆盖写入&#xff08;>&#xff09;&#xff1a; ./your_executable > logfile.txt这会将可执行文件的输…...

注册安全分析报告:北外网校

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…...

预警期刊命运逆袭到毕业好刊,仅45天!闭眼冲速度,发文量暴增!

选刊发表不迷路&#xff0c;就找科检易学术 期刊官网&#xff1a;Sustainability | An Open Access Journal from MDPI 1、期刊信息 期刊简介&#xff1a; Sustainability 是一本国际性的、同行评审的开放获取期刊&#xff0c;由MDPI出版社每半月在线出版。该期刊专注于人类…...

【LeetCode每日一题】——523.连续的子数组和

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 前缀和 二【题目难度】 中等 三【题目编号】 523.连续的子数组和 四【题目描述】 给你一个…...

leetcode54:螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示例 2&#xff1a; 输入&#xff1a;matrix [[1,2,3,…...

全方面熟悉Maven项目管理工具(三)认识mvn的各类构建命令并创建、打包Web工程

1. POM&#xff08;核心概念&#xff09; 1.1 含义 POM&#xff1a; Project Object Model&#xff0c;项目对象模型。 DOM&#xff1a; Document Object Model&#xff0c;文档对象模型&#xff0c;和 POM 类似 它们都是模型化思想的具体体现 1.2 模型化思想 POM 表示将…...

MySQL中查询语句的执行流程

文章目录 前言流程图概述最后 前言 你好&#xff0c;我是醉墨居士&#xff0c;今天我们一起探讨一下执行一条查询的SQL语句在MySQL内部都发生了什么&#xff0c;让你对MySQL内部的架构具备一个宏观上的了解 流程图 概述 对于查询语句的SQL的执行流程&#xff0c;主要可以分为…...

【代码随想录Day47】单调栈Part02

42. 接雨水 题目链接/文章讲解&#xff1a;代码随想录 视频讲解&#xff1a;单调栈&#xff0c;经典来袭&#xff01;LeetCode:42.接雨水_哔哩哔哩_bilibili 思路概述 问题理解&#xff1a;我们需要计算在给定柱子高度之间可以接住的雨水总量。雨水的量取决于柱子的高度和它们…...

Java全栈经典面试题剖析3】JavaSE面向对象2

目录 面试题2.12 Overload和Override的区别 面试题2.13 Overload方法是否可以改变返回值的类型&#xff1f; 面试题2.14 为什么方法不能根据返回类型来区分重载&#xff1f; 面试题2.15 构造器可不可以被重载或重写&#xff1f; 面试题2.16 在 Java 中定义⼀个不做事且没有…...

@JsonIgnoreProperties做接口对接时使用带来的好处

最近看到有个同事&#xff0c;在代码里面加了JsonIgnoreProperties这个注解&#xff0c;以前还真没有经常去用过&#xff0c;接口对接尤其是跟金蝶、用友等第三方&#xff0c;这个注解在接收数据是非常好用的&#xff1b;接下来带大家一起了解下具体的特性和使用方式 JsonIgno…...

SpringBoot整合mybatisPlus实现批量插入并获取ID

背景&#xff1a;需要实现批量插入并且得到插入后的ID。 使用for循环进行insert这里就不说了&#xff0c;在海量数据下其性能是最慢的。数据量小的情况下&#xff0c;没什么区别。 【1】saveBatch(一万条数据总耗时&#xff1a;2478ms) mybatisplus扩展包提供的&#xff1a;…...

实战RAG第一天——llama_index向量索引,查询引擎,搜索知识库问答,全部代码,保姆级教学

一、llama_index简介 llama_index(以前称为 GPT Index)是一个用于构建、查询、索引大型文档和数据集的开源框架。它的核心功能是帮助开发者将大语言模型(LLM)与自己的数据集无缝集成,从而进行知识库的构建、查询等任务。llama_index 使用 Python 编写,并结合了多种大语言…...

大数据治理

大数据治理是指对大数据的管理和控制,以确保数据的质量、可用性、安全性和合规性。随着大数据技术的不断发展,企业和组织面临着越来越多的数据管理挑战,如数据质量问题、数据安全问题、数据合规问题等。大数据治理成为了企业和组织应对这些挑战的重要手段。 一、大数据治理…...

云计算作业

关闭防火墙 停用Linux 挂载 下载nginx程序 启动nginx程序 连接网卡配置文件并且修改 更改模式为静态手动&#xff0c;并且分别修改ip地址&#xff0c;网关地址&#xff0c;dns 激活 创建自定义文件 定义server模块 监听地址 设置目录 匹配 激活网址根目录 创建目录文…...

复制文件到U盘提示:对于目标文件系统,文件过大

查看U盘属性的文件系统是否为FAT32&#xff0c;需将其改为NTFS 方法一 Win R 输入cmd打开命令行&#xff0c;输入以下命令&#xff08;注&#xff1a;f为U盘盘符&#xff09; convert f: /fs:ntfs /x方法二 格式化U盘&#xff0c;右键点击U盘进行格式化&#xff0c;文件系…...

SpringBoot+Swagger2.7.0实现汉化(2.8.0不行)

场景 SpringBootSwagger2实现可视化API文档流程&#xff1a; SpringBootSwagger2实现可视化API文档流程_swagger 可视化端口-CSDN博客 上面SpringBoot中使用swagger的效果 上面使用的是swagger2.8.0,且在线API是英文的。现在要将其进行汉化。 汉化效果 实现 首先打开sprin…...

c++ 散列表

散列表&#xff08;Hash Table&#xff09;是一种高效的数据结构&#xff0c;广泛用于实现快速的键值对存储。 基本概念 散列表使用哈希函数将键映射到数组的索引。其主要优点在于平均情况下提供常数时间复杂度的查找、插入和删除操作。 哈希函数: 将键映射到一个固定大小的…...

Windows通过netsh控制安全中心防火墙和网络保护策略

Windows通过netsh控制安全中心防火墙和网络保护策略 1. 工具简介 【1】. Windows安全中心 【2】. netsh工具 netsh(Network Shell) 是一个Windows系统本身提供的功能强大的网络配置命令行工具。 2. 开启/关闭防火墙策略 在设置端口&#xff08;禁用/启用&#xff09;前&am…...

UML(Unified Modeling Language,统一建模语言)

UML&#xff08;Unified Modeling Language&#xff0c;统一建模语言&#xff09;是一种标准化的图形化语言&#xff0c;用于软件工程中的可视化建模。UML由Grady Booch、James Rumbaugh和Ivar Jacobson共同开发&#xff0c;他们各自的工作&#xff08;Booch方法、OMT方法和OOS…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

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

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

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...