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

LeetCode_动态规划_中等_1749.任意子数组和的绝对值的最大值

目录

  • 1.题目
  • 2.思路
  • 3.代码实现(Java)

1.题目

给你一个整数数组 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

2.思路

(1)动态规划

  • 一个变量绝对值的最大值,可能是这个变量的最大值的绝对值,也可能是这个变量的最小值的绝对值。题目要求任意子数组和的绝对值的最大值,可以分别求出子数组和的最大值 positiveMax 和子数组和的最小值 negativeMin,因为子数组可以为空,所以 positiveMax ≥ 0negativeMin ≤ 0。最后返回 max⁡(positiveMax,−negativeMin) 即为任意子数组和的绝对值的最大值。
  • 而求子数组和的最大值,可以参照 53.最大子数组和的解法,运用动态规划求解。而求子数组和的最小值,也是类似的思路,遍历时记录全局最小值 negativeMin 和当前子数组负数和并更新,遍历完即可得到子数组和的最小值。

相关题目:
LeetCode_动态规划_简单_53.最大子数组和

3.代码实现(Java)

//思路1————动态规划
class Solution {public int maxAbsoluteSum(int[] nums) {int positiveMax = 0, negativeMin = 0;int positiveSum = 0, negativeSum = 0;for (int num : nums) {positiveSum += num;positiveMax = Math.max(positiveMax, positiveSum);positiveSum = Math.max(0, positiveSum);negativeSum += num;negativeMin = Math.min(negativeMin, negativeSum);negativeSum = Math.min(0, negativeSum);}return Math.max(positiveMax, -negativeMin);}
}

相关文章:

LeetCode_动态规划_中等_1749.任意子数组和的绝对值的最大值

目录 1.题目2.思路3.代码实现&#xff08;Java&#xff09; 1.题目 给你一个整数数组 nums 。一个子数组 [numsl, numsl1, …, numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 … numsr-1 numsr) 。请你找出 nums 中和的绝对值 最大的任意子数组&#xff08;可能为空…...

无涯教程-Perl - 环境配置

在开始编写Perl程序之前&#xff0c;让我们了解如何设置我们的Perl环境。 您的系统更有可能安装了perl。只需尝试在$提示符下给出以下命令- $perl -v 如果您的计算机上安装了perl&#xff0c;那么您将收到以下消息: This is perl 5, version 16, subversion 2 (v5.16.2) b…...

QT显示加载动画

文章目录 一、前言二、使用1.FormLoading.h2.FormLoading.cpp 一、前言 项目中在下发指令时&#xff0c;结果异步返回&#xff0c;可能需要一段时间&#xff0c;因此需要用到加载动画。 用的比较简单&#xff0c;就是新建Widget子窗口&#xff0c;放一个Label&#xff0c;使用…...

原型模式(C++)

定义 使用原型实例指定创建对象的种类&#xff0c;然后通过拷贝这些原型来创建新的对象。 应用场景 在软件系统中&#xff0c;经常面临着“某些结构复杂的对象”的创建工作;由于需求的变化&#xff0c;这些对象经常面临着剧烈的变化&#xff0c;但是它们却拥有比较稳定一致的…...

web浏览器打开本地exe应用

一、如何使web浏览器打开本地exe应用&#xff1f; 浏览器打开本地exe程序我们可以使用ActiveXObject方法&#xff0c;但是只支持IE&#xff0c;谷歌、火狐等浏览器并不支持此操作。 那问题来了&#xff0c;我们又该如何操作&#xff1f; 经过本博主的不断学习探索终于找到了一…...

微信小程序如何配置并使用less?

1&#xff0c;检查微信开发者工具&#xff08;工具版本1.03&#xff09;————这步很重要不然后面按步骤实行后会发现急死你也还是不管用&#xff0c;我之前死在过这一步&#xff0c;所以大家不要再次踩坑了 ~ ~ 。。。 2&#xff0c;在VScode中下载Less插件 3&#xff0c;…...

【Spring】反射动态修改Bean实例的私有属性值

Cannot cast org.springframework.http.client.InterceptingClientHttpRequestFactory to org.springframework.http.client.OkHttp3ClientHttpRequestFactory 由于RestTemplate在自定义初始化时顺序比较早&#xff0c;想在启动后跟进yum或者注解配置修改初始化的值时&#xff…...

MySQL DDL 数据定义

文章目录 1.创建数据库2.删除数据库3.查看所有数据库4.查看当前数据库5.选择数据库6.创建数据表7.查看 MySQL 支持的存储引擎和默认的存储引擎8.删除数据表9.查看数据库的数据表10.查看表结构11.查看建表语句12.重命名数据表13.增加、删除和修改字段自增长14.增加、删除和修改数…...

Ventoy 设置VTOY_MAX_SEARCH_LEVEL = 0只扫描U盘根目录 不扫码子目录

在镜像分区/media/yeqiang/Ventoy创建目录ventory&#xff0c;目录内创建文件ventoy.json&#xff0c;内容如下 {"control":[{ "VTOY_MAX_SEARCH_LEVEL": "0" }] }采用系统默认的utf-8编码。 参考&#xff1a; search path . Ventoy Plugin.e…...

vue3父子同信的双向数据实现

前言&#xff1a; 我们知道的是&#xff0c;父传子的通信&#xff0c;和子传父的通信&#xff0c;那如何实现父子相互通信的呢&#xff1f; (vue3中)v-model 和modelValue结合使用,在vue2中使用的是.sync 在父组件的写法 <template> <Son v-model"num" /&…...

Shiro是什么?为什么要用Shiro?

前言 本文小新为大家带来 Shiro入门概述 相关知识&#xff0c;具体内容包括Shiro是什么&#xff0c;为什么要用 Shiro&#xff0c;Shiro与Spring Security 的对比&#xff0c;Shiro的基本功能&#xff08;包括&#xff1a;基本功能框架&#xff0c;功能简介&#xff09;&#x…...

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

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

从零开始学Python(Ⅰ)基本变量与数据类型

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Python的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.关于Python的基本知识&#xff08;变量…...

SQL ASNI where from group order 顺序 where和having,SQL底层执行原理

SQL语句执行顺序&#xff1a; from–>where–>group by -->having — >select --> order 第一步&#xff1a;from语句&#xff0c;选择要操作的表。 第二步&#xff1a;where语句&#xff0c;在from后的表中设置筛选条件&#xff0c;筛选出符合条件的记录。 …...

Mac M2 Ventura(13.3) 新机 安装Cocoapods

1.执行命令&#xff1a; sudo gem install cocoapods 因为是新机&#xff0c;内置的ruby版本是&#xff08;2.6.0&#xff09;太低&#xff0c;会报错 所以需要安装新的ruby版本 2.如果已经安装了低版本的homebrew&#xff0c;可以先卸载&#xff1a; 卸载&#xff1a; /b…...

Unity 引擎做残影效果——2、屏幕后处理方式

Unity实现残影效果 大家好&#xff0c;我是阿赵。 这里继续介绍Unity里面做残影的方法。之前介绍了BakeMesh的方法做残影&#xff0c;这一期介绍的是用屏幕后处理的方法做残影。 一、原理 之前的BakeMesh方法&#xff0c;是真的生成了很多个网格模型在场景里面。如果用后处理做…...

考研算法38天:反序输出 【字符串的翻转】

题目 题目收获 很简单的一道题&#xff0c;但是还是有收获的&#xff0c;我发现我连scanf的字符串输入都忘记咋用了。。。。。我一开始写的 #include <iostream> #include <cstring> using namespace std;void deserve(string &str){int n str.size();int…...

“深入解析JVM:探秘Java虚拟机的工作原理“

标题&#xff1a;深入解析JVM&#xff1a;探秘Java虚拟机的工作原理 摘要&#xff1a;本文将深入探讨Java虚拟机&#xff08;JVM&#xff09;的工作原理&#xff0c;包括类加载、内存管理、垃圾回收、即时编译等关键概念。通过详细解析JVM的各个组成部分&#xff0c;读者将能够…...

[Flask]SSTI1

根据题目提示&#xff0c;这关应该是基于Python flask的模版注入&#xff0c;进入靶场环境后就是一段字符串&#xff0c;而且没有任何提示&#xff0c;有点难受&#xff0c;主要是没有提示注入点 随机尝试一下咯&#xff0c;首先尝试一下guest&#xff0c;GET传参 但是没有反应…...

Object Map 的相互转换

学生业务对象定义&#xff1a;Student Student student new Student(); student.setId(1L); student.setName("令狐冲") student.setAge(10) 第一种&#xff1a;通过Alibaba Fastjson实现 pom.xml 文件依赖 <dependency><groupId>com.alibaba</g…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...