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

【LeetCode 算法】Maximum Absolute Sum of Any Subarray 任意子数组和的绝对值的最大值-前缀和

文章目录

  • Maximum Absolute Sum of Any Subarray 任意子数组和的绝对值的最大值

Maximum Absolute Sum of Any Subarray 任意子数组和的绝对值的最大值

问题描述:

给你一个整数数组 nums 。一个子数组 [ n u m s l , n u m s l + 1 , . . . , n u m s r − 1 , n u m s r ] [nums_l, nums_{l+1}, ..., nums_{r-1}, nums_{r}] [numsl,numsl+1,...,numsr1,numsr] 的 和的绝对值 为 a b s ( n u m s l + n u m s l + 1 + . . . + n u m s r − 1 + n u m s r ) abs(nums_l + nums_{l+1} + ... + nums_{r-1} + nums_{r}) abs(numsl+numsl+1+...+numsr1+numsr)

请你找出 n u m s nums nums 中 和的绝对值 最大的任意子数组(可能为空),并返回该 最大值 。

abs(x) 定义如下:

如果 x 是负整数,那么 a b s ( x ) = − x abs(x) = -x abs(x)=x
如果 x 是非负整数,那么 a b s ( x ) = x abs(x) = x abs(x)=x

1 < = n u m s . l e n g t h < = 1 0 5 − 1 0 4 < = n u m s [ i ] < = 1 0 4 1 <= nums.length <= 10^5\\ -10^4 <= nums[i] <= 10^4 1<=nums.length<=105104<=nums[i]<=104

分析

暴力

最简单的方法就是枚举出所有可能的子数组,计算其和的绝对值,然后取max。但是子数组的数量规模是 N 2 N^2 N2,所以暴力会TLE,而且即使计算出了子数组,计算其和也是需要时间的。

因为最终需要知道子数组绝对值最大值。

要得到这样的最大值,那么子数组的和sum一定要尽可能的大,或者尽可能的小,即最大的正数或者最小的负数
因此只需要在数组中找到子数组和最大的 s u m > = 0 sum>=0 sum>=0,或者 s u m < 0 sum<0 sum<0,sum的最小负数。

到这里,就和某个问题很像了

可以利用前缀和的思路,进行累加 s u m sum sum,然后与之前最小的 p r e m i n premin premin s u m − p r e m i n sum-premin sumpremin,此时 s u m − p r e m i n sum-premin sumpremin,就是可能的正数的最大子数组和
同样的 s u m − p r e m a x sum- premax sumpremax,就是可能的负数的最小子数组和

代码

前缀和

public int maxAbsoluteSum(int[] nums) {int n = nums.length, ans = nums[0];int premax = 0,premin = 0;int sum = 0 ;for(int i = 0;i<n;i++){ sum += nums[i]; int a = sum - premin; // 非负数的最大int b = premax -sum;//负数的绝对值最大ans = Math.max(ans,Math.max(b,a));premin = Math.min(sum,premin);premax = Math.max(sum,premax);}return ans;}

时间复杂度 O ( N ) O(N) O(N)

空间复杂度 O ( 1 ) O(1) O(1)

前缀和

public int maxAbsoluteSum(int[] nums) {int s = 0, mx = 0, mn = 0;for (int x : nums) {s += x;// mx = Math.max(mx, s);// mn = Math.min(mn, s);if (s > mx) mx = s;else if (s < mn) mn = s; // 效率更高的写法}return mx - mn; }

时间复杂度 O ( N ) O(N) O(N)

空间复杂度 O ( 1 ) O(1) O(1)

灵神的代码更精简,不过他是从前缀和的另一个角度来看这个问题的,所以有点不一样。

Tag

Array

Presum

相关文章:

【LeetCode 算法】Maximum Absolute Sum of Any Subarray 任意子数组和的绝对值的最大值-前缀和

文章目录 Maximum Absolute Sum of Any Subarray 任意子数组和的绝对值的最大值问题描述&#xff1a;分析代码前缀和前缀和 Tag Maximum Absolute Sum of Any Subarray 任意子数组和的绝对值的最大值 问题描述&#xff1a; 给你一个整数数组 nums 。一个子数组 [ n u m s l ,…...

怎么建立大型语言模型

建立大型语言模型通常涉及以下主要步骤&#xff1a; 数据收集&#xff1a;收集大规模的文本数据作为模型的训练数据。可以从各种来源获取数据&#xff0c;如互联网、书籍、新闻文章等。数据的质量和多样性对于模型的性能至关重要。 数据预处理&#xff1a;对收集到的数据进行预…...

docker简介和安装

什么是docker&#xff1f; docker是基于Go语言编写的开源容器引擎&#xff0c;是操作系统级别的轻量级虚拟技术。主要用于应用打包、分发、部署。 打包&#xff1a;软件开发过程中&#xff0c;打包是将程序打包成软件包或者镜像的过程&#xff1b;在容器化程序中&#xff0c;打…...

记录问题: servlet获取项目包绝对路径

【2023-8-8 23:46:27 星期二】 如何获取在webapp下的路径?而不是target包下的webapp目录 比如这里应该获取到 F:\Tiam\Desktop\freemarker\freemarker-demo01\src\main\webapp 而readPath总是获取到 F:\Tiam\Desktop\freemarker\freemarker-demo01\target\freemarker-demo0…...

C语言文件操作基本方法

1、文件的分类 ANSI C 的缓冲文件系统 缓冲文件系统 缓冲文件系统是指&#xff0c;系统自动地在内存区为每个正在使用的文件开辟一个缓冲区。 从内存向磁盘输出数据时&#xff0c;必须首先输出到缓冲区中。待缓冲区装满后&#xff0c;再一起输出到磁盘文件中。 从磁盘文件向内…...

SQL 相关子查询 和 不相关子查询、Exists 、Not Exists、 多表连接(包含自连接)

不相关子查询 子查询的查询条件不依赖于父查询&#xff0c;称不相关子查询。子查询可以单独运行的 select stu_id,sex,age from student t where sex(select sexfrom studentwhere stu_id10023 )相关子查询 关联子查询 子查询的查询条件依赖于父查询&#xff0c;称为 相关子…...

项目规范 编写规范(范例)

项目目录 目录接口参考 项目目录结构设计&#xff0c;增加部分领域模型后缀强制定义&#xff0c;方便统一编码风格。 controller&#xff1a;请求处理 RestController module&#xff1a;按大业务区分&#xff0c;对多个业务对象数据聚合处理 Component manager&#xff1a;…...

MongoDB数据库操作及操作命令

目录 一、基础概念 二、安装mongod 三、命令交互数据库 &#xff08;1&#xff09;数据库命令 &#xff08;2&#xff09;集合命令 &#xff08;3&#xff09;文档命令 四、Mongoose &#xff08;1&#xff09;增加一条数据 &#xff08;2&#xff09;插入多个数据 &am…...

Linux命令(62)之tee

linux命令之tee 1.tee介绍 linux命令tee于读取标准输入的数据&#xff0c;并将内容输出为文件 2.tee用法 tee [参数] [filename] tee参数 参数说明-a读取标准输入的数据&#xff0c;并将内容追加到文件&#xff0c;而非覆盖-i忽略中断信号 3.实例 3.1.将ls -l输出内容作为…...

搭建Repo服务器

1 安装repo 参考&#xff1a;清华大学开源软件镜像站:Git Repo 镜像使用帮助 2 创建manifest仓库 2.1 创建仓库 git init --bare manifest.git2.2 创建default.xml文件 default.xml文件内容&#xff1a; <?xml version"1.0" encoding"UTF-8" ?…...

安卓:MMKV——键值存储库

目录 一、MMKV介绍 1.特点和优势&#xff1a; 2.使用指南&#xff1a; 3.依赖包&#xff1a; 二、MMKV的常用方法 1、初始化和获取实例&#xff1a; 2、存储数据&#xff1a; 3、读取数据 4、删除数据 5、其他操作&#xff1a; 三、MMKV的使用例子 MainActivity&#xff…...

使用Python将图像转换为PDF:一次性解决您的批量转换需求

导语&#xff1a; 在数字化时代&#xff0c;我们经常需要处理大量的图像文件。将这些图像转换为PDF格式可以方便地存档、分享和打印。本文将介绍如何使用Python编程语言将图像批量转换为PDF&#xff0c;并提供了一个简单易用的图形界面来跟踪转换进度。 准备工作 在开始之前…...

Vue——webpack

webpack 一、Install1.全局安装2.局部安装 二、总结1.打包2.定义脚本3.配置文件定义&#xff08;webpack.config.js)4.项目重新加载依赖5.webpack打包Css6.style-loader 一、Install 1.全局安装 npm install webpack webpack-cli -g2.局部安装 以项目为单位&#xff0c;一个项…...

springboot房地产管理java购房租房二手房j客户sp源代码mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 springboot房地产管理 系统1权限&#xff1a;管理员 …...

Gartner 发布影响数据科学和机器学习未来方向重要趋势

出品 | CSDN 云计算 供稿 | Gartner Gartner今日发布了影响数据科学与机器学习&#xff08;DSML&#xff09;未来方向的重要趋势。随着DSML行业的快速发展和演变&#xff0c;数据对于人工智能&#xff08;AI&#xff09;开发与运用的重要性日益提高&#xff0c;尤其是投资重点…...

72. 编辑距离

题目介绍 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例 1&#xff1a; 输入&#xff1a;word1 "horse", word2 &q…...

Android12.0 原生系统SystemUI下拉状态栏和通知栏视图之锁屏通知布局

1.前言 在12.0的系统rom定制化开发中,对于系统原生systemui的锁屏界面的功能也是非常重要的,所以在锁屏页面布局中,也是有通知栏布局的,所以接下来对于息屏亮屏 通知栏布局的相关流程分析,看下亮屏后锁屏页面做了哪些功能 2.原生系统SystemUI下拉状态栏和通知栏视图之锁…...

周末在家值班,解决几个月前遗忘的Bug

问题&#xff1a; 周末被迫在家值班&#xff0c;无聊之际打开尘封已久的Bug清单&#xff0c;发现有Bug拖了几个月还没解决… 场景是这样子的&#xff0c;有个功能是拿Redis缓存热点数据进行展示&#xff0c;暂且称它为功能A&#xff0c;有个另外的功能B&#xff0c;它会去更新缓…...

Shell编程基础(十五)文本三剑客(sed)

文本三剑客&#xff08;sed&#xff09; 使用场景基本语法实例命令列表 使用场景 sed提供了一种面交互的方式修改文件内容。 它是一行一行处理&#xff0c;可以通过正则匹配要修改的部分 基本语法 基本语法 sed [-opt] command files(多个文件 空格隔开) sed 使用正则 sed -…...

5,二叉树【p6-p7】

二叉树 5.1二叉树5.1.1例1&#xff1a;用递归和非递归两种方式实现二叉树的先序、中序、后序遍历5.1.1.1递归序的先序、中序、后序遍历先序遍历&#xff1a;中序遍历&#xff1a;后序遍历&#xff1a; 5.1.1.2非递归序的先序、中序、后序遍历先序遍历&#xff1a;中序遍历&…...

GinCdn内容分发系统V1.0.9更新内容

GinCdn内容分发系统GinCdn是一款基于Go语言Gin框架自研的轻量高效内容分发系统&#xff0c;专为中小型企业/个人搭建CDN打造&#xff0c;采用主控边缘节点分布式架构&#xff0c;实现智能调度、高效缓存、精准监控的一体化解决方案。无需复杂命令行&#xff0c;小白也能轻松上手…...

程序运行机制:编译、链接与装入详解

1. 程序运行的底层机制解析作为一名在嵌入式系统开发领域工作多年的工程师&#xff0c;我经常需要深入理解程序从源代码到最终执行的完整过程。这个看似简单的"程序运行"背后&#xff0c;实际上隐藏着编译、链接、装入这三个关键阶段。今天&#xff0c;我就结合自己的…...

深度解析BG3ModManager:博德之门3模组加载顺序重置问题的架构设计与解决方案

深度解析BG3ModManager&#xff1a;博德之门3模组加载顺序重置问题的架构设计与解决方案 【免费下载链接】BG3ModManager A mod manager for Baldurs Gate 3. 项目地址: https://gitcode.com/gh_mirrors/bg/BG3ModManager BG3ModManager作为《博德之门3》的核心模组管理…...

Multisim仿真避坑指南:振幅调制器设计时,如何搞定静态工作点和输出幅度?

Multisim仿真实战&#xff1a;振幅调制器设计的5个关键调试技巧 在电子工程课程设计中&#xff0c;振幅调制器是一个经典但充满挑战的项目。许多学生在Multisim仿真阶段就会遇到各种问题——静态工作点不稳定、输出波形失真、峰峰值不达标...这些问题往往让初学者感到挫败。本文…...

Python开发者实战:用pg-mcp轻松搞定PostgreSQL集群读写分离与连接池管理

Python开发者实战&#xff1a;用pg-mcp轻松搞定PostgreSQL集群读写分离与连接池管理 现代Web应用对数据库的要求越来越高&#xff0c;特别是在高并发场景下&#xff0c;传统的单一数据库连接方式往往成为性能瓶颈。作为Python开发者&#xff0c;我们经常需要在Flask或Django项目…...

C++ ONNX Runtime推理踩坑记:为什么我的全局Session一Run就报ORT_RUNTIME_EXCEPTION?

C ONNX Runtime推理异常解析&#xff1a;全局Session与Env生命周期的陷阱 在C项目中使用ONNX Runtime进行模型推理时&#xff0c;许多开发者都遇到过这样一个令人困惑的场景&#xff1a;明明代码逻辑看起来完全正确&#xff0c;却在调用Session.Run()时突然抛出ORT_RUNTIME_EXC…...

基于YOLOv8深度学习的花卉识别检测系统(YOLOv8+YOLO数据集+UI界面+Python项目源码+模型)

一、项目介绍 随着计算机视觉技术的快速发展&#xff0c;基于深度学习的图像识别技术在植物分类与识别领域展现出巨大的应用潜力。本系统基于先进的YOLOv8目标检测算法&#xff0c;构建了一个高效准确的花卉识别检测系统&#xff0c;能够实现对13种不同花卉的实时检测与识别。…...

扩散模型之(十八)ControlNet 原理与指南

概述在当今瞬息万变的科技环境中&#xff0c;如何在人类创造力和机器精确性之间取得平衡变得日益重要。而这正是我们ControlNet发挥作用的地方——它如同“引导之手”&#xff0c;为基于扩散的文本到图像合成模型提供指导&#xff0c;从而解决传统图像生成模型中常见的局限性。…...

FPGA新手必看:Vivado 2023.1里用DDS IP核生成1MHz正弦波,附完整仿真代码

FPGA实战&#xff1a;从零构建1MHz正弦波生成器的Vivado全流程解析 刚拿到FPGA开发板时&#xff0c;我最想实现的第一个项目就是信号发生器。看着示波器上跳动的波形从自己编写的代码中产生&#xff0c;这种成就感无可替代。本文将带你用Xilinx Vivado 2023.1中的DDS IP核&…...

在大厂工作,一旦开窍后,你会爽死…

在职场尤其是大厂里&#xff0c;沟通能力往往比硬实力更能决定你的发展节奏。很多时候&#xff0c;同样一件事&#xff0c;不同的说法&#xff0c;会带来完全不同的结果。下面这8个高频职场场景&#xff0c;对应的高情商话术&#xff0c;帮你轻松化解尴尬、刷好感&#xff0c;还…...