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

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

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

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...