力扣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 <= 1051 <= 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.length1 <= 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…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
