当前位置: 首页 > 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…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Mobile ALOHA全身模仿学习

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

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...