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

leetcode 1749.任意子数组和的绝对值的最大值

思路:dp

说到绝对值,大家肯定不陌生,但是用在dp上就会使问题变得稍微复杂一些了。

我们在最大子数组和的那道题中知道,在状态转移的时候,我们会舍弃掉为负数的连续部分,重新构建连续的子串。但是,这里不一样,我们并不能轻易舍弃负数的部分,负数也可能让这个子数组和的绝对值变成最大的,例如0,-1000,1,2这个序列就很典型,我们如果按照上一个题那样做,就会使最大值变成3,而不是1000。

这里给出的思路,就是把最大子数组和与最小子数组和之间,两者分别取绝对值,然后比较谁大这个思路,这样就能考虑到最大子数组和中没有考虑到的把负数加进来的讨论了。

这里用了两个dp数组,一个代表最大子数组和,一个代表最小子数组和。

上代码:

class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {vector<int>dp1(nums.size()+1,0);vector<int>dp2(nums.size()+1,0);dp1[0]=nums[0];dp2[0]=nums[0];int ans=max(abs(dp1[0]),abs(dp2[0]));for(int i=1;i<nums.size();i++){if(dp1[i-1]<=0)dp1[i]=nums[i];if(dp2[i-1]<=0)dp2[i]=dp2[i-1]+nums[i];if(dp1[i-1]>0)dp1[i]=nums[i]+dp1[i-1];if(dp2[i-1]>0)dp2[i]=nums[i];ans=max(ans,max(abs(dp1[i]),abs(dp2[i])));}return ans;}
};

相关文章:

leetcode 1749.任意子数组和的绝对值的最大值

思路&#xff1a;dp 说到绝对值&#xff0c;大家肯定不陌生&#xff0c;但是用在dp上就会使问题变得稍微复杂一些了。 我们在最大子数组和的那道题中知道&#xff0c;在状态转移的时候&#xff0c;我们会舍弃掉为负数的连续部分&#xff0c;重新构建连续的子串。但是&#xf…...

Linux进程——进程地址空间

前言&#xff1a;在讲完环境变量后&#xff0c;相信大家对Linux有更进一步的认识&#xff0c;而Linux进程概念到这也快接近尾声了&#xff0c;现在我们了解Linux进程中的地址空间&#xff01; 本篇主要内容&#xff1a; 了解程序地址空间 理解进程地址空间 探究页表和虚拟地址空…...

基于 LlaMA 3 + LangGraph 在windows本地部署大模型 (三)

基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;三&#xff09; 大家继续看 https://lilianweng.github.io/posts/2023-06-23-agent/的文档内容 第二部分&#xff1a;内存 记忆的类型 记忆可以定义为用于获取、存储、保留以及随后检索信息的过程。人脑中有多…...

python3如何安装bs4

在python官网找到beautifulsoup模块的下载页面&#xff0c;点击"downloap"将该模块的安装包下载到本地。 将该安装包解压&#xff0c;然后在打开cmd&#xff0c;并通过cmd进入到该安装包解压后的文件夹目录下。 在该文件目录下输入"python install setup.py&quo…...

docker容器技术篇:rancher管理平台部署kubernetes集群

rancher管理平台部署kubernetes集群 Rancher 是一个 Kubernetes 管理工具&#xff0c;让你能在任何地方和任何提供商上部署和运行集群。 Rancher 可以创建来自 Kubernetes 托管服务提供商的集群&#xff0c;创建节点并安装 Kubernetes&#xff0c;或者导入在任何地方运行的现…...

【计算机网络原理】初识网络原理和一些名词解释​​

˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…...

车载电子电器架构 —— 关于bus off汇总

车载电子电器架构 —— 关于bus off汇总 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明…...

Linux函数

目录 一、脚本函数 1.1 创建函数 1.2 使用函数 二、函数返回值 2.1 默认的退出状态码 2.2 使用return命令 2.3 使用函数输出 三、在函数中使用变量 3.1 向函数传达参数 3.2 在函数中处理变量 四、数组变量和函数 4.1 向函数中传递数组 4.2 从函数中返回数组 五、函数…...

如何查看centos7中Java在哪些路径下

在 CentOS 7 上&#xff0c;你可以通过几种方式查找安装的 Java 版本及其路径。以下是一些常用的方法&#xff1a; 1. 使用 alternatives 命令 CentOS 使用 alternatives 系统来管理同一命令的多个版本。你可以使用以下命令来查看系统上所有 Java 安装的配置&#xff1a; su…...

信息安全-古典密码学简介

目录 C. D. Shannon: 一、置换密码 二、单表代替密码 ① 加法密码 ② 乘法密码 ③密钥词组代替密码 三、多表代替密码 代数密码 四、古典密码的穷举分析 1、单表代替密码分析 五、古典密码的统计分析 1、密钥词组单表代替密码的统计分析 2、英语的统计规…...

面试题 01.05. 一次编辑

字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串&#xff0c;编写一个函数判定它们是否只需要一次(或者零次)编辑。 示例 1: 输入: first "pale" second "ple" 输出: True示例 2: 输入: first &qu…...

针对头疼的UDP攻击如何定制有效的防护措施

分布式拒绝服务攻击&#xff08;Distributed Denial of Service&#xff09;简称DDoS&#xff0c;亦称为阻断攻击或洪水攻击&#xff0c;是目前互联网最常见的一种攻击形式。DDoS攻击通常通过来自大量受感染的计算机&#xff08;即僵尸网络&#xff09;的流量&#xff0c;对目标…...

怎么制作流程图?介绍制作方法

怎么制作流程图&#xff1f;在日常生活和工作中&#xff0c;流程图已经成为我们不可或缺的工具。无论是项目规划、流程优化&#xff0c;还是学习理解复杂系统&#xff0c;流程图都能帮助我们更直观地理解和表达信息。然而&#xff0c;很多人可能并不清楚&#xff0c;其实制作流…...

棱镜七彩参编《网络安全技术 软件供应链安全要求》国家标准发布

据全国标准信息公共服务平台消息显示&#xff0c;《网络安全技术 软件供应链安全要求》&#xff08;GB/T 43698-2024&#xff09;国家标准已于2024年4月25日正式发布&#xff0c;并将于2024年11月1日正式实施。棱镜七彩作为主要编制单位之一参与该国家标准的编制&#xff0c;为…...

Keepalived实现LVS高可用

6.1 KeepalivedLVS集群介绍 Keepalived和LVS共同构建了一个高效的负载均衡和高可用性解决方案&#xff1a;LVS作为负载均衡器&#xff0c;负责在集群中的多个服务器间分配流量&#xff0c;以其高性能和可扩展性确保应用程序能够处理大量的并发请求&#xff1b;而Keepalived则作…...

【力扣】1089.复写零

原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不…...

Golang实践录:gin框架使用自定义日志模块

本文介绍在 Golang 的 gin 框架中使用自定义日志模块的一些方法。 背景 很早之前就实现并使用了自己封装的日志模块&#xff0c;但一直没有将gin框架内部的日志和日志模块结合。gin的日志都是在终端上打印的&#xff0c;排查问题不方便。趁五一假期&#xff0c;集中研究把此事…...

Django之配置数据库

一&#xff0c;创建项目 二&#xff0c;将项目的setting.py中的 DATABASES {default: {ENGINE: django.db.backends.sqlite3,NAME: BASE_DIR / db.sqlite3,} }替换成如下&#xff08;以mysql为例&#xff09; DATABASES {default: {ENGINE: django.db.backends.mysql,NAME: …...

Ajax 笔记02

01 jq中的ajax方法中的dataType属性 dataType属性的属性值有以下几种: xml 返回数据按照xml解析 json 返回的数据按照json代码解析 script 返回的数据按照js代码解析 text 把返回的数据按照普通文本解析 jsonp 跨域 json: javascript object notation(js对象简谱) json整体…...

【隧道篇 / WAN优化】(7.4) ❀ 03. WAN优化的原理 ❀ FortiGate 防火墙

【简介】相信对WAN优化感兴趣的人都会有疑问&#xff0c;WAN优化真的有作用吗&#xff1f;如果真的有作用&#xff0c;那是根据什么原理呢&#xff1f;让我们来更深入的了解一下。 客户端和服务器端 其实很多人在一开始看到WAN优化这个词&#xff0c;就自然的以为上网速度太慢&…...

RTX 4090D专属镜像应用场景:短视频MCN机构批量生成口播视频生产系统

RTX 4090D专属镜像应用场景&#xff1a;短视频MCN机构批量生成口播视频生产系统 1. 短视频行业的痛点与解决方案 短视频MCN机构每天面临的最大挑战之一&#xff0c;就是如何高效生产大量高质量的口播视频内容。传统制作流程通常需要&#xff1a; 租用专业摄影棚聘请主播录制…...

HDMI设备开发必看:EDID/E-EDID数据结构全解析(附实战代码)

HDMI设备开发实战&#xff1a;EDID/E-EDID二进制解析与工程实现 当你的HDMI设备无法正确识别显示器分辨率时&#xff0c;屏幕闪烁或黑屏的瞬间是否让你抓狂&#xff1f;作为连接数字世界的桥梁&#xff0c;EDID&#xff08;Extended Display Identification Data&#xff09;就…...

三菱电机MR-J5伺服系统实战:如何用CC-Link IE TSN搭建高效生产线(附配置清单)

三菱电机MR-J5伺服系统实战&#xff1a;CC-Link IE TSN智能产线部署指南 在工业4.0的浪潮中&#xff0c;生产线的智能化升级已成为制造业提升竞争力的关键。作为这一变革的核心驱动技术&#xff0c;三菱电机MR-J5系列伺服系统凭借其支持CC-Link IE TSN网络的独特优势&#xff0…...

开发者专属OpenClaw配置:nanobot镜像对接VSCode插件开发

开发者专属OpenClaw配置&#xff1a;nanobot镜像对接VSCode插件开发 1. 为什么选择nanobot镜像进行VSCode插件开发 去年我在开发一个智能代码补全插件时&#xff0c;发现市面上大多数AI辅助工具都存在响应延迟高、隐私性差的问题。直到接触到OpenClaw生态下的nanobot镜像&…...

轻量级工具G-Helper:一站式解决ROG游戏本色彩配置异常问题

轻量级工具G-Helper&#xff1a;一站式解决ROG游戏本色彩配置异常问题 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目…...

LFM2.5-1.2B-Thinking-GGUF开源可部署:自主可控轻量模型替代方案深度评测

LFM2.5-1.2B-Thinking-GGUF开源可部署&#xff1a;自主可控轻量模型替代方案深度评测 1. 模型概述 LFM2.5-1.2B-Thinking-GGUF是Liquid AI推出的轻量级文本生成模型&#xff0c;专为低资源环境优化设计。该模型采用GGUF格式存储&#xff0c;配合llama.cpp运行时&#xff0c;能…...

Ryujinx开源项目:跨平台Switch游戏模拟解决方案

Ryujinx开源项目&#xff1a;跨平台Switch游戏模拟解决方案 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx 在数字化娱乐日益普及的今天&#xff0c;如何让Nintendo Switch游戏突破硬件…...

跨平台终端工具cmatrix:打造震撼的数字雨可视化效果

跨平台终端工具cmatrix&#xff1a;打造震撼的数字雨可视化效果 【免费下载链接】cmatrix Terminal based "The Matrix" like implementation 项目地址: https://gitcode.com/gh_mirrors/cm/cmatrix 你是否曾幻想过在自己的终端中重现《黑客帝国》里令人着迷的…...

s2-pro部署实操:CSDN平台GPU资源监控与s2-pro服务性能关联分析

s2-pro部署实操&#xff1a;CSDN平台GPU资源监控与s2-pro服务性能关联分析 1. 专业语音合成工具s2-pro简介 s2-pro是Fish Audio开源的专业级语音合成模型镜像&#xff0c;它能够将文本转换为自然流畅的语音&#xff0c;并支持通过参考音频来复用特定音色。这个工具特别适合需…...

从预处理指令看跨语言兼容:手把手封装C++库供C调用的5个关键步骤

从预处理指令看跨语言兼容&#xff1a;手把手封装C库供C调用的5个关键步骤 在嵌入式开发和SDK设计中&#xff0c;经常需要将C库封装成C语言接口。这种跨语言调用看似简单&#xff0c;实则暗藏玄机。本文将深入剖析extern "C"和__cplusplus预处理指令的底层原理&#…...