LeetCode解法汇总1749. 任意子数组和的绝对值的最大值
目录链接:
力扣编程题-解法汇总_分享+记录-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;}
};
相关文章:
LeetCode解法汇总1749. 任意子数组和的绝对值的最大值
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的…...
4.2、Flink任务怎样读取文件中的数据
目录 1、前言 2、readTextFile(已过时,不推荐使用) 3、readFile(已过时,不推荐使用) 4、fromSource(FileSource) 推荐使用 1、前言 思考: 读取文件时可以设置哪些规则呢? 1. 文件的格式(tx…...
Effective Java笔记(28)列表优于数组
数组与泛型相比,有两个重要的不同点 。 首先,数组是协变的( covariant ) 。 这个词听起来有点吓人,其实只是表示如果 Sub 为 Super 的子类型,那么数组类型 Sub[ ]就是Super[ ]的子类型。 相反,泛…...
做BI领域的ChatGPT,思迈特升级一站式ABI平台
8月8日,以「指标驱动 智能决策」为主题,2023 Smartbi V11系列新品发布会在广州丽思卡尔顿酒店开幕。 后疫情时代,BI发展趋势的观察与应对 在发布会上,思迈特CEO吴华夫在开场致辞中表示,当前大环境背景下…...
ELFK——ELK结合filebeat日志分析系统(2)
目录 一、filebeat 二、ELFK 1.原理简介 2.在ELK基础上部署filebeat 一、filebeat Filebeat,轻量级的开源日志文件数据搜集器。通常在需要采集数据的客户端安装 Filebeat,并指定目录与日志格式,Filebeat 就能快速收集数据,并…...
webSocket 协议是什么
webSocket 协议是什么,能简述一下吗? websocket 协议 HTML5 带来的新协议,相对于 http,它是一个持久连接的协议,它利用 http 协议完成握手,然后通过 TCP 连接通道发送消息,使用 websocket 协议可…...
CentOS 7迁移Anolis OS 8
背景:生产环境客户要求操作系统国产化 操作系统:Centos7.9 内核:5.4.108 服务器可以联网,进行在线迁移: # 下载迁移工具软件源 wget https://mirrors.openanolis.cn/anolis/migration/anolis-migration.repo -O /etc/y…...
Transformer 立体视觉 Depth Estimation
1. Intro 立体深度估计具有重要的意义,因为它能够重建三维信息。为此,在左右相机图像之间匹配相应的像素;对应像素位置的差异,即视差,可以用来推断深度并重建3D场景。最近基于深度学习的立体深度估计方法已经显示出有希望的结果,但仍然存在一些挑战。 其中一个挑战涉及使…...
vue去掉所有输入框两边空格,封装指令去空格,支持Vue2和Vue3,ElementUI Input去空格
需求背景 就是页面很多表单输入框,期望在提交的时候,都要把用户两边的空格去掉 ❌使用 vue 的指令 .trim 去掉空格 中间会输入不了空格, 比如我想输入 你好啊 中国, 这中间的空格输入不了,只能变成 你好啊中国 ❌在提交的时候使用…...
认识FFMPEG框架
FFMPEG全称: Fast Forward Moving Picture Experts Group (MPEG:动态图像专家组) ffmpeg相关网站: git://source.ffmpeg.org/ffmpeg.git http://git.videolan.org/?pffmpeg.git https://github.com/FFmpeg/FFmpeg FFMPEG框架基本组件: AVFormat , AVCodec, AVDevice, AVFil…...
Vue3 大屏数字滚动效果
父组件: <template> <div class"homePage"> <NumRoll v-for"(v, i) in numberList" :key"i" :number"v"></NumRoll> </div> </template> <script setup> import { onMounted, r…...
【深度学习注意力机制系列】—— SENet注意力机制(附pytorch实现)
深度学习中的注意力机制(Attention Mechanism)是一种模仿人类视觉和认知系统的方法,它允许神经网络在处理输入数据时集中注意力于相关的部分。通过引入注意力机制,神经网络能够自动地学习并选择性地关注输入中的重要信息ÿ…...
go 函数
go 语言函数 go 函数函数定义Go函数的特点如下函数作为参数可变参数相同类型可变参数不同类型可变参数 return语句作用概述空的return语句空白标识符多个返回值命名返回值 defer 语句作用引申出来的面试题for defer下面是一个使用defer的示例代码输出结果 匿名函数定义匿名函数…...
python之正则表达式
目录 正则表达式 python正则表达式方法 match search findall finditer compile 元字符匹配 元字符 量词 贪婪匹配和惰性匹配 正则表达式的group 语法 案例 正则表达式 正则表达式又称规则表达式,是使用单个字符串来描述、匹配某个句法规则的字符串…...
【LeetCode每日一题】——219.存在重复元素II
文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 哈希表 二【题目难度】 简单 三【题目编号】 219.存在重复元素II 四【题目描述】 给你一个…...
篇六:适配器模式:让不兼容变兼容
篇六:“适配器模式:让不兼容变兼容” 开始本篇文章之前先推荐一个好用的学习工具,AIRIght,借助于AI助手工具,学习事半功倍。欢迎访问:http://airight.fun/ 另外有2本不错的关于设计模式的资料,…...
【云原生】Docker-compose中所有模块学习
compose模块 模板文件是使用 Compose 的核心,涉及到的指令关键字也比较多。但大家不用担心,这里面大部分指令跟 docker run 相关参数的含义都是类似的。 默认的模板文件名称为 docker-compose.yml,格式为 YAML 格式。 version: "3&quo…...
广义积分练习
前置知识 无穷限积分瑕积分 练习 计算 ∫ 0 ∞ 1 x ( 1 x ) d x \int_0^{\infty}\dfrac{1}{\sqrt x(1x)}dx ∫0∞x (1x)1dx 解: x 0 \qquad x0 x0为瑕点 \qquad 原式 lim a → 0 lim b → ∞ ∫ a b 1 x ( 1 x ) d x lim a → 0 lim …...
element-ui树形表格,左边勾选,右边显示选中的数据-功能(如动图)
功能如图 功能需求 表格树形表格勾选数据,右边显示对应勾选的数据内容,选中客户,自动勾选所有的店铺(子级),选中其中一个店铺,自动勾选上客户(父级),同时会存在只有客户(下面没有子级的情况&am…...
Android数字价格变化的动画效果的简单实现
原理:使用ValueAnimator属性动画类实现,它通过值的改变手动设置对象的属性值来实现动画效果。直接贴代码: public static void doNumberAnim(TextView tvPrice, float startNumber, float endNumber) {ValueAnimator animator ValueAnimato…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
