​LeetCode解法汇总1749. 任意子数组和的绝对值的最大值

news/2024/4/19 0:05:07

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。

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

abs(x) 定义如下:

  • 如果 x 是负整数,那么 abs(x) = -x 。
  • 如果 x 是非负整数,那么 abs(x) = x 。

示例 1:

输入:nums = [1,-3,2,3,-4]
输出:5
解释:子数组 [2,3] 和的绝对值最大,为 abs(2+3) = abs(5) = 5 。

示例 2:

输入:nums = [2,-5,1,-4,3,-2]
输出:8
解释:子数组 [-5,1,-4] 和的绝对值最大,为 abs(-5+1-4) = abs(-8) = 8 。

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

解题思路:

/**

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

* 1,-3,2,3,-4

* 2,-5,1,-4,3,-2

* 解题思路:

* 动态规划,构建2个数组dp1和dp2,dp1[i]代表数组右区间为i位,可能的最大的正数数组和,dp2[i]则为负数。

* 遍历的时候,如果nums[i+1] + dp1[i]>0,则dp1[i+1]=nums[i+1] + dp1[i],否则dp1[i+1]=0。dp2也是一样的逻辑。

* 找dp1和dp2最大的绝对值即可。

*/

代码:

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


http://www.ppmy.cn/news/1014237.html

相关文章

Vue3+Vite+Pinia+Naive后台管理系统搭建之九:layout 动态路由布局

前言 如果对 vue3 的语法不熟悉的&#xff0c;可以移步Vue3.0 基础入门&#xff0c;快速入门。 1. 系统页面结构 由 menu&#xff0c;面包屑&#xff0c;用户信息&#xff0c;页面标签&#xff0c;页面内容构建 ​ 2. 创建页面 创建 src/pages/layout.vue 布局页 创建 sr…

docker-compose 部署elk,别找了,这是最好的教程

通过docker-compose编排一系列环境进行一键快速部署运行&#xff0c;小白运维神器。 # 安装git命令&#xff1a; yum install -y git git clone https://gitee.com/zhengqingya/docker-compose.git cd docker-compose/Linux环境部署见每个服务下的run.md&#xff1b; eg: Linu…

2024考研408-计算机网络 第五章-传输层学习笔记

文章目录 前言一、传输层提供的服务1.1、传输层的功能1.2、传输层的两个协议&#xff08;TCP、UDP&#xff09;1.3、传输层的寻址与端口&#xff08;常见端口介绍&#xff09; 二、UDP协议2.1、认识UDP功能和特点2.2、UDP首部格式2.3、UDP伪首部字段分析2.4、伪首部校验UDP用户…

ESD接地实时监控系统有哪些功能

ESD接地实时监控系统是一种用于监测和维护静电放电&#xff08;ESD&#xff09;接地的设备和软件系统。静电放电事件可能会对敏感电子元件、设备或工作环境造成损害&#xff0c;因此对ESD接地进行有效的监控至关重要。 ESD接地实时监控系统主要包括以下几个方面的功能&#xf…

本地构建包含java和maven的镜像

目录 1.前提条件 2.下载 2.1.创建Dockerfile 3.构建镜像 参考文章 1.前提条件 本地环境需要的系统和软件 win10 Docker Desktop Powershell 图1 Win10安装Docker后&#xff0c;直接在Powershell使用Docker命令 有些Developer不习惯win10系统&#xff0c;却想要使用Lin…

war和war exploded

war和war exploded的区别 war模式&#xff1a;将WEB工程以包的形式上传到服务器 &#xff1b; war exploded模式&#xff1a;将WEB工程以当前文件夹的位置关系上传到服务器&#xff1b;>> war包是自己打包生成的&#xff0c;如pom文件中<packaging>war</packag…

基于java校园爱心捐赠互助管理系统设计与实现

摘 要 随着互联网及电子商务平台的飞速发展&#xff0c;利用在线平台实现的二手商品交易以及在线捐赠已经非常普遍&#xff0c;很多高校目前还存在贫困生需要通过爱心人士的捐助来完成学业&#xff0c;同时很多高校的大学生也希望借助自己的捐赠行为来帮助到身边需要帮助的同学…

【数学】协方差介绍、相关系数介绍,Python代码

协方差 协方差&#xff08;Covariance&#xff09;是统计学中用来衡量两个随机变量之间关系的一种度量。它反映了这两个变量的变化趋势是否一致&#xff0c;即当一个变量偏离其均值时&#xff0c;另一个变量是否也倾向于偏离其均值。协方差可以帮助我们了解变量之间的线性关系…

AutoSAR系列讲解(实践篇)12.5-Dem

目录 一、Dem简介 二、Dem消抖 1、计数模式 1. 普通增减计数 2. 反向归零增减模式

Live Market:AI赋能跨境产业,把握世界财富新周期

AI技术的应用也成为了推动跨境电商产业进一步发展的关键因素之一。例如&#xff0c;GPT这样的自然语言处理技术&#xff0c;被广泛应用于跨境电商的运营和管理中。GPT可以通过文本分析和生成技术&#xff0c;帮助企业优化客户服务、提高搜索引擎排名等方面&#xff0c;提升企业…

构造函数打开文件怎么处理打开失败的情况?

如下的一个类&#xff1a;如何处理文件打开失败的情况&#xff0c;谢谢 /*** DictParser is used to parse a file* it parse a line every time*/ class DictParser { public:DictParser(std::string path) : _fs(path) {};~DictParser() {_fs.close();}void add_column(Parse…

世界算力简史(上)

1946年2月14日&#xff0c;在美国宾夕法尼亚州东南部的费城&#xff0c;人们正在像以往一样正常工作和生活。 忽然&#xff0c;他们发现&#xff0c;房间里的灯暗了下来。 刚刚经历过二战的人们&#xff0c;对这种情况习以为常。他们心想&#xff1a;“是不是哪里的电力线路又坏…

洛谷P1162 - 填涂颜色

题目描述 由数字 0 0 0 组成的方阵中&#xff0c;有一任意形状闭合圈&#xff0c;闭合圈由数字 1 1 1 构成&#xff0c;围圈时只走上下左右 4 4 4 个方向。现要求把闭合圈内的所有空间都填写成 2 2 2。例如&#xff1a; 6 6 6\times 6 66 的方阵&#xff08; n 6 n6 n6&…

springboot vue 初步集成onlyoffice

文章目录 前言一、vue ts1. 安装依赖2. onlyoffice组件实现3. 使用组件4. 我的配置文件 二、springboot 回调代码1. 本地存储 三、效果展示踩坑总结 前言 对接onlyoffice&#xff0c;实现文档的预览和在线编辑功能。 一、vue ts 1. 安装依赖 npm install --save onlyoffi…

web集群学习:源码安装nginx配置启动服务脚本、IP、端口、域名的虚拟主机

目录 1、源码安装nginx&#xff0c;并提供服务脚本。 2、配置基于ip地址的虚拟主机 3、配置基于端口的虚拟主机 4、配置基于域名的虚拟主机 1、源码安装nginx&#xff0c;并提供服务脚本。 1、源码安装会有一些软件依赖 &#xff08;1&#xff09;检查并安装 Nginx 基础依赖…

24届近5年同济大学自动化考研院校分析

今天给大家带来的是同济大学控制考研分析 满满干货&#xff5e;还不快快点赞收藏 一、同济大学 学校简介 同济大学历史悠久、声誉卓著&#xff0c;是中国最早的国立大学之一&#xff0c;是教育部直属并与上海市共建的全国重点大学。经过115年的发展&#xff0c;同济大学已经…

【面试八股文】每日一题:谈谈你对集合的理解

每日一题-Java核心-谈谈你对集合的理解【面试八股文】 谈谈你对集合的理解 Java集合是Java编程语言中用于存储数据的容器。它提供了一系列的类和接口&#xff0c;用于操作和管理数据集合。Java集合框架主要包括以下几个重要的接口和类&#xff1a; List&#xff1a;List是一个有…

报错Error: error:0308010C:digital envelope routines::unsupported

Error: error:0308010C:digital envelope routines::unsupported 解决&#xff1a; 在原有脚本前加&#xff1a; SET NODE_OPTIONS--openssl-legacy-provider && 原来&#xff1a; 加后&#xff1a;

【halcon】paint_region , write_image 和 compose3

背景 我在现场采集图片&#xff0c;需要初步筛选出NG和OK的图片&#xff0c;我发现得到NG的原图后&#xff0c;肉眼看不到哪里NG了&#xff0c;或者说很难找。这个时候&#xff0c;我想保存NG的同时再保存一张标记了NG位置的图片。 算子使用 paint_region (SelectedRegions1…

富文本上传图片及回显功能

1、首先安装依赖 wangEditor vue3安装依赖 yarn add wangeditor/editor-for-vuenext # 或者 npm install wangeditor/editor-for-vuenext --save 2、根据实际情况&#xff08;看接口是否要转成base64格式&#xff09; <div style"border: 1px solid #ccc">…