力扣9.30
1749. 任意子数组和的绝对值的最大值
给你一个整数数组 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.length <= 105
-104 <= nums[i] <= 104
分析
最大子数组和的变式,可以求处最大子数组和和最小子数组和,然后取绝对值的max
代码
typedef long long LL;
class Solution {
public:const static int N = 1e5 + 5, INF = 0x3f3f3f3f;int dp1[N], dp2[N];int maxAbsoluteSum(vector<int>& nums) {int n = nums.size();int res = 0;dp1[0] = -INF;dp2[0] = INF; for(int i = 1; i <= n; i ++ ) {dp1[i] = max(nums[i - 1], dp1[i - 1] + nums[i - 1]);dp2[i] = min(nums[i - 1], dp2[i - 1] + nums[i - 1]);res = max(res, abs(dp1[i]));res = max(res, abs(dp2[i]));}return res;}
};
1191. K 次串联后最大子数组之和
给定一个整数数组 arr
和一个整数 k
,通过重复 k
次来修改数组。
例如,如果 arr = [1, 2] , k = 3
,那么修改后的数组将是 [1, 2, 1, 2, 1, 2]
。
返回修改后的数组中的最大的子数组之和。注意,子数组长度可以是 0
,在这种情况下它的总和也是 0
。
由于 结果可能会很大,需要返回的 109 + 7
的 模 。
数据范围
1 <= arr.length <= 105
1 <= k <= 105
-104 <= arr[i] <= 104
分析
分类讨论,两种情况,对于k=1的情况,直接在长度为n的数组上做一次子数组最大和,对于k>1的情况,可能会出现起点和终点不在同一个区间内,因此需要对数组进行复制,而对于中间是否需要加上一整段区间,只需要看数组的和是否为正数,若是正数,则一定可以将整段区间插入到起点和终点之间。
代码
typedef long long LL;
class Solution {
public:const static LL N = 1e5 + 5, INF = 0x3f3f3f3f, mod = (LL)1e9 + 7;LL res = 0;LL dp[2 * N];LL kConcatenationMaxSum(vector<int>& arr, int k) {int n = arr.size();LL sum = 0;for(int i = 0; i < n; i ++ ) {sum += arr[i];sum %= mod;}dp[0] = 0;for(int i = 1; i <= n * (k > 1 ? 2 : 1); i ++ ) {dp[i] = max((LL)0, dp[i - 1] + (LL)arr[(i - 1) % n]);if(sum > 0 && k >= 2) res = max(res, dp[i] + sum * (k - 2) % mod);else res = max(res, dp[i]);dp[i] %= mod;res %= mod;}return res % mod;}
};
918. 环形子数组的最大和
给定一个长度为 n
的环形整数数组 nums
,返回 nums
的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i]
的下一个元素是 nums[(i + 1) % n]
, nums[i]
的前一个元素是 nums[(i - 1 + n) % n]
。
子数组 最多只能包含固定缓冲区 nums
中的每个元素一次。形式上,对于子数组 nums[i], nums[i + 1], ..., nums[j]
,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n
。
数据范围
n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
分析
令dp[i]
表示以i结尾的最大子数组和,同时用len[i]
记录长度,对于环形,我们可以开两倍数组将首位相接,然后跑一边最大子数组和并记录长度,若长度大于n
,则说明需要删去首部一些点,由于我们已经记录了子数组的长度,所以可以轻松找到这段子数组的开头,之后找到前缀和小于0的最小值mins
,将dp[i]
减去mins
,同时更新len
即可
代码
class Solution {
public:const static int N = 3e4 + 5, INF = 0x3f3f3f3f;int dp[2 * N];int len[2 * N];int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();int res = -INF;dp[0] = -INF;for(int i = 1; i <= 2 * n; i ++ ) {if(dp[i - 1] + nums[(i - 1) % n] > nums[(i - 1) % n]) {dp[i] = dp[i - 1] + nums[(i - 1) % n];len[i] = len[i - 1] + 1;} else {dp[i] = nums[(i - 1) % n];len[i] = 1;}if(len[i] > n) {int t = len[i];int last = i - t + 1;while(i - last + 1 > n) {dp[i] -= nums[(last - 1) % n];last ++ ;}int minsum = 0, sum = 0;int pos = last - 1;for(int k = last; k <= i; k ++ ) {sum += nums[(k - 1) % n];if(minsum > sum) {minsum = sum;pos = k;}}len[i] = i - pos;dp[i] -= minsum;}res = max(res, dp[i]);}return res;}
};
相关文章:
力扣9.30
1749. 任意子数组和的绝对值的最大值 给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 ... numsr-1 numsr) 。 请你找出 nums 中 和的绝对值 最大的任意子数组(可能为空),…...
kafka下载配置
下载安装 参开kafka社区 zookeeperkafka消息队列群集部署https://apache.csdn.net/66c958fb10164416336632c3.html 下载 kafka_2.12-3.2.0安装包快速下载地址分享 官网下载链接地址: 官网下载地址:https://kafka.apache.org/downloads 官网呢下载慢…...
nlp任务之预测中间词-huggingface
目录 1.加载编码器 1.1编码试算 2.加载数据集 3.数据集处理 3.1 map映射:只对数据集中的sentence数据进行编码 3.2用filter()过滤 单词太少的句子过滤掉 3.3截断句子 4.创建数据加载器Dataloader 5. 下游任务模型 6.测试预测代码 7.训练代码 8.保…...
《程序猿之Redis缓存实战 · Redis 与数据库一致性》
📢 大家好,我是 【战神刘玉栋】,有10多年的研发经验,致力于前后端技术栈的知识沉淀和传播。 💗 🌻 CSDN入驻不久,希望大家多多支持,后续会继续提升文章质量,绝不滥竽充数…...
【无标题】observer: error while loading shared libraries: libmariadb.so.3处理办法
文章目录 1.记录新装的oceanbase,使用observer帮助时,出现lib文件无法找到的处理过程 ./observer --help ./observer: error while loading shared libraries: libmariadb.so.3: cannot open shared object file: No such file or directory2.做一个strace跟踪&…...
极客兔兔Gee-Cache Day1
极客兔兔7Days GeeCache - Day1 interface{}:任意类型 缓存击穿:一个高并发的请求查询一个缓存中不存在的数据项,因此这个请求穿透缓存直接到达后端数据库或数据源来获取数据。如果这种请求非常频繁,就会导致后端系统的负载突然…...
[MAUI]数据绑定和MVVM:MVVM的属性验证
一、MVVM的属性验证案例 Toolkit.Mvvm框架中的ObservableValidator类,提供了属性验证功能,可以使用我们熟悉的验证特性对属性的值进行验证,并将错误属性提取和反馈给UI层。以下案例实现对UI层的姓名和年龄两个输入框,进行表单提交验证。实现效果如下所示 View<ContentP…...
2024年水利水电安全员考试题库及答案
一、判断题 1.采用水下钻孔爆破方案时,侧面应采用预裂爆破,并严格控制单响药量以保护附近建(构)筑物的安全。 答案:正确 2.围堰爆破拆除工程的实施应成立爆破指挥机构,并应按设计确定的安全距离设置警戒。…...
【快速删除 node_modules 】rimraf
目录 1. 什么是node_modules 2. 卸载一个npm包 3. 删除 node_modules 为什么这么慢 4. rimraf 5. 为什么rimraf 这么快 作为前端开发,无论我们关注不关注,每天都能接触到node_modules。通常产生于一个npm install命令,之后就不会多加关注…...
毕业设计选题:基于ssm+vue+uniapp的教学辅助小程序
开发语言:Java框架:ssmuniappJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:M…...
13-指针和动态内存-内存泄漏
一、视频笔记: C语言通过malloc,来获取堆上的内存。 动态调用内存: malloc 和 free ;new 和 delete 都行。 内存泄漏指的是我们动态申请了内存,但是即是是使用完了之后(从来都不去释放它)。只…...
基于深度学习的视频摘要生成
基于深度学习的视频摘要生成是一种通过自动化方式从长视频中提取关键片段,生成简洁且有代表性的视频摘要的技术。其目的是在保留视频主要内容的基础上,大幅缩短视频的播放时长,方便用户快速理解视频的核心信息。以下是视频摘要生成的主要方法…...
适合初学者的[JAVA]: 基础面试题
目录 说明 前言 String/StringBuffer/StringBuilder区别 第一点: 第二点: 总结: 反射机制 JVM内存结构 运行时数据区域被划分为5个主要组件: 方法区(Method Area) 堆区(Heap Area) 栈区&#x…...
internal.KaptWithoutKotlincTask$KaptExecutionWorkAction 问题 ---Room数据库
Caused by: java.lang.Exception: No native library is found for os.nameMac and os.archaarch64. path/org/sqlite/native/Mac/aarch64 m3 目前使用的是MAC M3芯片的配置会出现这个问题。M1就应该就有这个问题 解决: 在project层级的build.gradle中的allprojec…...
Frequency-aware Feature Fusion for Dense Image Prediction 论文阅读
摘要:密集图像预测任务要求具有强类别信息和高分辨率精确空间边界细节的特征。为了实现这一点,现代分层模型通常利用特征融合,直接添加来自深层的上采样粗特征和来自较低层次的高分辨率特征。在本文中,我们观察到融合特征值在对象内的快速变化…...
Springboot + netty + rabbitmq + myBatis
目录 0.为什么用消息队列1.代码文件创建结构2.pom.xml文件3.三个配置文件开发和生产环境4.Rabbitmq 基础配置类 TtlQueueConfig5.建立netty服务器 rabbitmq消息生产者6.建立常规队列的消费者 Consumer7.建立死信队列的消费者 DeadLetterConsumer8.建立mapper.xml文件9.建立map…...
电磁兼容(EMC):整改案例(四)人体对EFT测试影响有多大?
目录 1. 异常现象 2. 原因分析 3. 整改方案 4. 总结 1. 异常现象 某产品按GB/T 17626.4标准进行电快速瞬变脉冲群测试,测试条件为:频率5kHz/100kHz,测试电压L,N线间2kV,L,N线对PE线4kV。测试过程中需要…...
数据可视化基础:让数据说话
一、引言 在信息洪流中,数据可视化如同灯塔,照亮了数据的海洋,让我们能够洞察数据背后的意 义。 下面是对数据可视化的详细介绍,包括定义、作用、类型、原则、工具方法以及应用场景, 并附上具体的代码示例。 二、数…...
有哪些优化数据库性能的方法?如何定位慢查询?数据库性能优化全攻略:从慢查询定位到高效提升
在现代应用程序开发中,数据库的性能对于整体系统的响应能力至关重要。随着用户数量的增加和数据量的增长,如何优化数据库性能、定位慢查询成了每一个开发者面临的重要挑战。今天,我想和大家分享一些实用的数据库性能优化方法,以及…...
C语言 | Leetcode C语言题解之第450题删除二叉搜索树中的节点
题目: 题解: struct TreeNode* deleteNode(struct TreeNode* root, int key){struct TreeNode *cur root, *curParent NULL;while (cur && cur->val ! key) {curParent cur;if (cur->val > key) {cur cur->left;} else {cur c…...
智慧防灾,科技先行:EasyCVR平台助力地质灾害视频监测系统建设
随着科技的飞速发展,视频监控技术已成为地质灾害监测与预警的重要手段之一。在众多视频监控平台中,EasyCVR视频汇聚平台凭借其强大的视频整合、实时传输、视频处理及分发等能力,在地质灾害场景中展现出显著的应用优势。 一、实时监测与远程监…...
掌握C#核心概念:类、继承、泛型等
C# 是一门功能强大且灵活的面向对象编程语言,它结合了许多现代编程语言的特点和特性。无论你是编程新手,还是有经验的开发者,理解C#中的核心概念都是非常重要的。本文将介绍C#中的类与对象、构造函数和析构函数、方法的重载与重写、继承与多态…...
[VULFOCUS刷题]tomcat-pass-getshell 弱口令
tomcat-pass-getshell 弱口令 启动容器,打开网站 点开manageapp,输入弱口令 tomcat/tomcat 之后在下面上传jsp大马,首先生成一个jsp马 这里我直接使用github别人生成好的 tennc/webshell: This is a webshell open source project (github.…...
golang rpc
RPC(Remote Procedure Call)远程过程调用,简单的理解是一个节点请求另一个节点提供的服务,对应rpc的是本地过程调用,函数调用是最常用的本地过程调用,将本地过程调用变成远程调用会面临着各种问题。 以两数…...
A Learning-Based Approach to Static Program Slicing —— 论文笔记
A Learning-Based Approach to Static Program Slicing OOPLSA’2024 文章目录 A Learning-Based Approach to Static Program Slicing1. Abstract2. Motivation(1) 为什么需要能处理不完整代码(2) 现有方法局限性(3) 验证局限性: 初步实验研究实验设计何为不完整代码实验结果…...
掌握 C# 中的委托与事件机制
C# 中的委托和事件为开发者提供了处理回调、异步编程以及发布订阅模式的强大工具。委托与事件机制在实际应用中非常常见,特别是在事件驱动编程和 GUI 应用中。本文将带你深入理解委托的定义、匿名方法、Lambda 表达式、事件机制以及多播委托的使用。 1. 委托&#x…...
使用微服务Spring Cloud集成Kafka实现异步通信(消费者)
1、本文架构 本文目标是使用微服务Spring Cloud集成Kafka实现异步通信。其中Kafka Server部署在Ubuntu虚拟机上,微服务部署在Windows 11系统上,Kafka Producer微服务和Kafka Consumer微服务分别注册到Eureka注册中心。Kafka Producer和Kafka Consumer之…...
docker pull 超时Timeout失败的解决办法
当国内开发者docker pull遇到如下提示时,不要惊讶 [rootvm /]# docker pull postgres Using default tag: latest Error response from daemon: Get "https://registry-1.docker.io/v2/": dial tcp 128.121.146.235:443: i/o timeout [rootvm /]# 自2024…...
YOLOv7改进之主干DAMOYOLO结构,结合 CReToNeXt 结构,打造高性能检测器
一、DAMOYOLO理论部分 论文地址:2211.15444 (arxiv.org) 在本报告中,我们提出了一种快速准确的对象检测方法,称为 DAMO-YOLO,它实现了比最先进的 YOLO 系列更高的性能。DAMO-YOLO 是从 YOLO 扩展而来的,具有一些新技术,包括神经架构搜索 (NAS)、高效的重新参数化广义 …...
进度条(倒计时)Linux
\r回车(回到当前行开头) \n换行 行缓冲区概念 什么现象? 什么现象?? 什么现象??? 自己总结: #pragma once 防止头文件被重复包含 倒计时 在main.c中,windows.h是不可以用的&…...
蓝色政府网站/html简单网页代码
接上篇,有人说不使用super,不就行了,但是netty是需要你super的 public class WangNetty45Server { private static final Logger LOGGER LoggerFactory.getLogger(WangNetty45Server.class); public void start(int port){ …...
濮阳网络电视台直播/seo基础知识包括什么
Simple Tree Model Example 简单树模型示例 The Simple Tree Model example shows how to use a hierarchical model with Qts standard view classes. 简单树模型示例显示了如何将分层模型与Qt的标准视图类一起使用。 Qts model/view architecture provides a standard way…...
龙口市规划建设局网站/阿里云免费域名
head 标签作用: HTML head 元素 规定文档相关的配置信息(元数据),包括文档的标题,引用的文档样式和脚本等。 head 标签中放的元素 1、title 网页的标题,title将会被显示在浏览器的标题栏,或…...
网站规划/重庆网站优化
需求:后端返回数据流,前端进行下载。 1.定义js文件,包含所有的blobType export const blobType {xls: application/vnd.ms-excel,xlsx: application/vnd.openxmlformats-officedocument.spreadsheetml.sheet,csv: text/csv,doc: applicatio…...
一品威客网怎么接单/seo关键词如何布局
咱先来聊聊Redis 像Redis的基础入门,掌握下图这几个列出来的知识点足以了。 进阶的话,就得下点功夫了,事务、主从复制、哨兵、集群等等之类的搞不明白你就上不去呀。 再看美团亿级流量Redis实战,Redis分布式锁、session、缓存与数…...
长沙企业网站建设公司/抖音搜索排名优化
案例需求 ——公司在文件服务器中新安装了RHEL5操作系统,由于默认启动的服务程序较多,系统运行缓慢。现需要对系统服务进行适当优化,减少一些不必要的自启动服务,并设置系统在开机后直接进入字符模式运行 需求描述 设置Linux系统每…...