当前位置: 首页 > 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;就自然的以为上网速度太慢&…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...