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

【力扣每日一题】2023.8.8 任意子数组和的绝对值的最大值

目录

题目:

示例:

分析:

代码:


题目:

示例:

分析:

题目给我们一个数组,让我们找出它的绝对值最大的子数组的和。

这边的子数组是要求连续的,让我们找出一个元素之和的绝对值最大的连续子数组。

要绝对值最大,那么就是两种情况,最大的正数以及最小的负数,所以我们可以兵分两路,一次寻找正数的最大值,一次寻找负数的最小值。

我们很容易就能想到使用滑动窗口,右窗口滑动用来吸收新的数,而左窗口滑动用来吐出不要的数。我们要使用滑动窗口就必须要搞清楚左窗口什么时候滑动,滑动到什么时候停止。

我们先看看怎么寻找正数的最大值,我们的右窗口一直往右扩张,直到如果窗口内的总和为负数了,那么目前为止的窗口总和就变成“累赘”了,因为我们要的是寻找最大的正数,一旦有负数了,我们就把窗口全部丢弃,从右窗口的右边再接着“滑动”。

那可能有人会问,为什么是把窗口全部丢弃,而不是开始滑动左窗口。

因为窗口的总和变为负数,这一结果是右窗口吸收新元素造成的,因此我们不需要的元素一定是靠近右窗口的,如果开始滑动左窗口,那么一开始滑出的只会是我们需要的正数,总和只会越来越小,直到左窗口和右窗口重叠,窗口总和变成0,然后再接着从右窗口的右边接着“滑动”。

大家可能发现了,在本题中,我们的左窗口没有存在的必要,因为它不需要滑动,每次更新都是直接更新到右窗口的位置,所以我们只需要用一根指针来遍历原数组即可,此外还需要用两个变量,分别接收当前“窗口”内的正数最大值和我们已经获取到的正数的最大值。每次移动指针我们都判断当前“窗口”的总和有没有小于0,小于0就抛弃掉当前窗口,将窗口总和置为0,重新开始“滑动”。

那我们说完了怎么获取正数的最大值,还有一个就是要获取负数的最小值,这个也是上面的步骤,只不过是改变一下判断条件,就是判断当前窗口的总和有没有大于0,大于0就抛弃掉当前窗口,将窗口总和置为0,重新开始“滑动”。

上面两种可以同时进行,只是各自需要两个变量来分别记录和更新。

最后再比较一下,把正数的最大值和负的负数的最小值中最大的返回出去即可。

代码:

class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {int maxRes=abs(nums[0]),minRes=abs(nums[0]);int tempMax=0,tempMin=0;for(int& num:nums){if(tempMax+num<=0) tempMax=0;else tempMax+=num;if(tempMin+num>=0) tempMin=0;else tempMin+=num;if(tempMin<minRes) minRes=tempMin;if(tempMax>maxRes) maxRes=tempMax;}return max(maxRes,-minRes);}
};

相关文章:

【力扣每日一题】2023.8.8 任意子数组和的绝对值的最大值

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一个数组&#xff0c;让我们找出它的绝对值最大的子数组的和。 这边的子数组是要求连续的&#xff0c;让我们找出一个元素之和…...

SpringBoot Web开发静态资源处理

Web开发探究 简介 其实SpringBoot的东西用起来非常简单&#xff0c;因为SpringBoot最大的特点就是自动装配 使用SpringBoot的步骤&#xff1a; 1、创建一个SpringBoot应用&#xff0c;选择我们需要的模块&#xff0c;SpringBoot就会默认将我们的需要的模块自动配置好 2、手动…...

Dockerfile定制Tomcat镜像

Dockerfile中的打包命令 FROM &#xff1a; 以某个基础镜像作为此镜像的基础 RUN &#xff1a; RUN后面跟着linux常用命令&#xff0c;如RUN echo xxx >> xxx,注意&#xff0c;RUN 不能用于执行命令&#xff0c;因为每个RUN都是独立运行的&#xff0c;RUN 的cd对镜像中的…...

【计算机网络】概述及数据链路层

每一层只依赖于下一层所提供的服务&#xff0c;使得各层之间相互独立、灵活性好&#xff0c;已于实现和维护&#xff0c;并能促进标准化工作。 应用层&#xff1a;通过应用进程间的交互完成特定的网络应用&#xff0c;HTTP、FTP、DNS&#xff0c;应用层交互的数据单元被称为报…...

Java——基础语法(二)

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 「推荐专栏」&#xff1a; ★java一站式服务 ★ ★ React从入门到精通★ ★前端炫酷代码分享 ★ ★ 从0到英雄&#xff0c;vue成神之路★ ★ uniapp-从构建到提升★ ★ 从0到英雄&#xff…...

数据结构----算法--分治,快速幂

数据结构----算法–分治,快速幂 一.分治 1.分治的概念 分治法&#xff1a;分而治之 将一个问题拆解成若干个解决方式完全相同的问题 满足分治的四个条件 1.问题难度随着数据规模缩小而降低 2.问题可拆分 3.子问题间相互独立 4.子问题的解可合并 2.二分查找(折半搜索)…...

【ChatGPT 指令大全】怎么使用ChatGPT写履历和通过面试

目录 怎么使用ChatGPT写履历 寻求履历的反馈 为履历加上量化数据 把经历修精简 为不同公司客制化撰写履历 怎么使用ChatGPT通过面试 汇整面试题目 给予回馈 提供追问的问题 用 STAR 原则回答面试问题 感谢面试官的 email 总结 在职场竞争激烈的今天&#xff0c;写一…...

微服务:从header中获取用户存入当前线程

1、从网关gateway工程filter中解析token携带的当前用户信息并添加到header中 //获取token携带的idObject userid claimsBody.get("id");//在header中添加新的信息ServerHttpRequest serverHttpRequest request.mutate().headers(httpHeaders -> {httpHeaders.ad…...

C语言系列之原码、反码和补码

一.欢迎来到我的酒馆 讨论c语言中&#xff0c;原码、反码、补码。 目录 一.欢迎来到我的酒馆二.原码 二.原码 2.1在计算机中&#xff0c;所有数据都是以二进制存储的&#xff0c;但不是直接存储二进制数&#xff0c;而是存储二进制的补码。原码很好理解&#xff0c;就是对应的…...

程序框架——UI管理模块

UI基类BasePanel 负责帮助我们通过代码快速的找到所有的子控件&#xff0c;方便我们在子类中处理逻辑&#xff0c;节约找控件的工作量。 public class BasePanel : MonoBehaviour {//通过里式转换原则 来存储所有的控件private Dictionary<string, List<UIBehaviour>…...

MySQL 慢查询探究分析

目录 背景&#xff1a; mysql 整体结构&#xff1a; SQL查询语句执行过程是怎样的&#xff1a; 知道了mysql的整体架构&#xff0c;那么一条查询语句是怎么被执行的呢&#xff1a; 什么是索引&#xff1a; 建立索引越多越好吗&#xff1a;   如何发现慢查询&#xff1…...

wpf 项目中使用 Prism + MaterialDesign

1.通过nuget安装MaterialDesign 2.通过nuget安装Prism 3.修改App.xmal <prism:PrismApplication x:Class"VisionMeasureGlue.App"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/…...

【Spring Boot】Thymeleaf模板引擎 — Thymeleaf页面布局

Thymeleaf页面布局 熟悉Thymeleaf的语法和表达式后&#xff0c;后面开发起来会更加得心应手。接下来好好研究一下Thymeleaf如何实现完整的Web系统页面布局。 1.引入代码片段 在模板中经常希望包含来自其他模板页面的内容&#xff0c;如页脚、页眉、菜单等。为了做到这一点&a…...

整理mongodb文档:删

个人博客 整理mongodb文档:删 求关注&#xff0c;哪儿不足&#xff0c;求大佬们指出&#xff0c;哪儿写的不够通俗易懂跟清晰&#xff0c;也求指出 文章概叙 本文主要是介绍了删除数据的几个方法&#xff0c;主要还是在介绍deleteMany、deleteOne以及remove&#xff0c;对于…...

篇二十三:设计模式的综合实例:构建完整项目

篇二十三&#xff1a;"设计模式的综合实例&#xff1a;构建完整项目" 开始本篇文章之前先推荐一个好用的学习工具&#xff0c;AIRIght&#xff0c;借助于AI助手工具&#xff0c;学习事半功倍。欢迎访问&#xff1a;http://airight.fun/。 另外有2本不错的关于设计模…...

FFmpeg常见命令行(三):FFmpeg转码

前言 在Android音视频开发中&#xff0c;网上知识点过于零碎&#xff0c;自学起来难度非常大&#xff0c;不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》。本文是Android音视频任务列表的其中一个&#xff0c; 对应的要学习的内容是&#xff1a;如何使…...

合宙Air724UG LuatOS-Air script lib API--scanCode

Table of Contents scanCode scanCode.request(cbFnc, timeout) scanCode 模块功能&#xff1a;扫码. 支持二维码、条形码扫描 scanCode.request(cbFnc, timeout) 设置扫码请求 参数 名称 传入值类型 释义 cbFnc function 扫码返回或者超时未返回的回调函数&#xff0c;回调…...

2023年新手如何学剪辑视频 想学视频剪辑如何入门

随着短视频、vlog等媒体形式的兴起&#xff0c;视频剪辑已经成为了热门技能。甚至有人说&#xff0c;不会修图可以&#xff0c;但不能不会剪视频。实际上&#xff0c;随着各种智能软件的发展&#xff0c;视频剪辑已经变得越来越简单。接下来&#xff0c;一起来看看新手如何学剪…...

C++的auto究竟是何方神圣

C的auto究竟是何方神圣 前言&#x1f64c;auto&#xff08;C 11&#xff09; 的使用细则auto是什么&#xff1f; auto声明的变量是在什么时期被编译器推导出来呢&#xff1f;为什么使用auto进行定义变量时&#xff0c;必须进行初始化&#xff1f; auto 的使用场景auto与指针和引…...

网络安全【黑客】面试题汇总

前言 一眨眼2023年已经过去一大半&#xff0c;不知道大家有没有找到心仪的工作。作为一个安全老鸟&#xff0c;工作这么多年&#xff0c;面试过很多人也出过很多面试题目&#xff0c;也在网上收集了各类关于渗透面试题目&#xff0c;里面有我对一些问题的见解&#xff0c;希望…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...