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

【算法-动态规划】、魔法卷轴: 两次清零机会整个数组最大累加和

news 来源：原创 2025/5/16 21:54:15

文章目录

一、dp
- 1.1 题意理解
- 1.2 整体思路
- 1.3 具体思路
- 1.4 代码
二、多语言解法

一、dp

1.1 题意理解

nums 数组, 有正负0, 使用最多两次魔法卷轴, 希望使数组整体的累加和尽可能大. 求尽可能大的累加和
其实就是需要分情况讨论, 可能使用0/1/2个魔法卷轴
使用的效果: 把 nums 连续的一段全变为0

1.2 整体思路

分情况讨论:
0. 若使用0次魔法卷轴, 则答案即为全数组的累加和

若使用1次魔法卷轴, 对于 dp[i] 来说, 分为如下情况"要或不要":
1.1 要 nums[i], 则 dp[i] = dp[i-1] + nums[i]. 因为要 nums[i] 则说明在 i 位置没有使用魔法卷轴, 而目标是必须使用1次魔法卷轴, 则必然在 dp[i-1] 即前 i-1 内用那1次魔法卷轴
1.2 不要 nums[i], 说明 i 位置会使用魔法卷轴, 但魔法卷轴可以是一段区间而不是一个点, 所以需要看从 i 位置向前到哪个位置(如i-1, i-2, …等) 都需使用魔法卷轴. 本质是哪个位置的前缀和最大, 则截止到哪. 例如若 presum[i-3] 最大, 则 i-2, i-1, i 都使用魔法卷轴即可.
若使用2次魔法卷轴, 则对 i 来说, 在 nums[0…i-1] 用一次, 在 nums[i…n-1] 再用一次

1.3 具体思路

用0次魔法卷轴, 求出整个数组的和
求前缀和 presum[i] = sum(nums[0…i-1]), 求后缀和 sufsum[i] = sum(nums[i…n-1])
用1次魔法卷轴, dp[i] 可根据 dp[i-1] 和 nums[i] 和 presum[i] 求出
用2次魔法卷轴, dp[i] 可根据 presum[i] 和 sufsum[i] 求出

1.4 代码

package mainimport ("fmt""math""math/rand"
)func main() {fmt.Println("测试开始")n, v := 50, 10times := 10000for range times {sz := rand.Intn(n)nums := randArr(sz, v)a := f1(nums)b := f2(nums)if a != b {panic("匹配失败")}}fmt.Println("完全匹配成功")
}// dp
func f1(nums []int) int {n := len(nums)if n == 0 {return 0}// 用 0 次卷轴p0 := 0for _, v := range nums {p0 += v}// 基础数据// prefix[i] 表示从 0~i 范围内, 必须用 1 次卷轴, 0~i范围的最大累加和prefix := make([]int, n)prefix[0] = 0            // 0~0 范围内只有 nums[0] 一个数, 而且还用了卷轴, 所以整个数组的累加和肯定是 0sum := nums[0]           // 每一步的前缀和maxPresum := max(0, sum) // 各步 前缀和的最大值, 若整个数组都是负数, 则 maxPresum 应为 0for i := 1; i < n; i++ {prefix[i] = max(prefix[i-1]+nums[i], maxPresum) // 前者留 nums[i], 后者不留 nums[i]sum += nums[i]maxPresum = max(maxPresum, sum)}// 必须用 1 次卷轴p1 := prefix[n-1]// 基础数据// suffix[i] 表示从 i~n-1 范围内, 必须用 1 次卷轴, i~n-1范围的最大累加和suffix := make([]int, n)suffix[n-1] = 0         // n-1~n-1范围内只有 nums[n-1] 一个数, 而且还用了卷轴, 所以整个数组的累加和肯定是 0sum = nums[n-1]         // 每一步的前缀和maxPresum = max(0, sum) // 各步 前缀和的最大值, 若整个数组都是负数, 则 maxPresum 应为 0for i := n - 2; i >= 0; i-- {suffix[i] = max(suffix[i+1]+nums[i], maxPresum) // 前者留 nums[i], 后者不留 nums[i]sum += nums[i]maxPresum = max(maxPresum, sum)}// 必须用 2 次卷轴// 即遍历 i, 在 0~i-1范围内必须用 1 次, 在 i~n-1 范围内必须再用 1 次p2 := math.MinIntfor i := 1; i < n; i++ { // 注意, i 必须从 1 开始, 否则 0~i-1 范围是非法的p2 = max(p2, prefix[i-1]+suffix[i])}return max(p0, p1, p2)
}// 暴力法
func f2(nums []int) int {n := len(nums)p0 := 0for _, v := range nums {p0 += v}p1 := mustOneScroll(nums, 0, n-1)p2 := 0// 枚举划分点for i := range n {p2 = max(p2, mustOneScroll(nums, 0, i-1)+mustOneScroll(nums, i, n-1))}return max(p0, p1, p2)
}// 暴力辅助函数: 必须用 1 次卷轴
func mustOneScroll(nums []int, l, r int) int {ans := math.MinInt// 枚举划分点 l...a...b...r-1, 使 a...b 之间使用卷轴// 在 a...b 左比右闭区间使用卷轴for a := l; a <= r; a++ {for b := a; b <= r; b++ { // b 可能等于 a, 因为必须使用 1 次卷轴curAns := 0for i := l; i < a; i++ { // 不含 acurAns += nums[i]}for i := b + 1; i < r; i++ { // 不含 bcurAns += nums[i]}ans = max(ans, curAns)}}return ans
}func randArr(n, v int) []int {ans := make([]int, n)for i := range ans {ans[i] = rand.Intn(v)}return ans
}

参考代码

二、多语言解法

$Cpp / G o / P y t h o n / R u s t / J s / T s$

// cpp

// go 同上

# python

// rust

// js

// ts

【算法-动态规划】、魔法卷轴: 两次清零机会整个数组最大累加和

【算法-动态规划】、魔法卷轴: 两次清零机会整个数组最大累加和文章目录一、dp1.1 题意理解1.2 整体思路1.3 具体思路1.4 代码二、多语言解法一、dp 1.1 题意理解 nums 数组, 有正负0, 使用最多两次魔法卷轴, 希望使数组整体的累加和尽可能大. 求尽可能大的累加和其实就…...

编程日记 2025/5/16 21:54:15

蓝桥杯C语言组：分治问题研究

蓝桥杯C语言组分治问题研究摘要本文针对蓝桥杯C语言组中的分治问题展开深入研究，详细介绍了分治算法的原理、实现方法及其在解决复杂问题中的应用。通过对经典例题的分析与代码实现，展示了分治算法在提高编程效率和解决实际问题中的重要作用&#xff…...

编程日记 2025/5/16 21:11:49

npm介绍（Node Package Manager）（JavaScript生态中最流行的包管理工具，主要用于Node.js项目的依赖管理）

文章目录 **核心功能****常用命令****关键文件****npm vs 其他工具****最佳实践**官方资源 npm（Node Package Manager）是 JavaScript 生态中最流行的包管理工具，主要用于 Node.js 项目的依赖管理。以下是核心要点： 核心功能依赖管…...

编程日记 2025/5/13 18:39:29

小白零基础如何搭建CNN

1.卷积层在PyTorch中针对卷积操作的对象和使用的场景不同，如有1维卷积、2维卷积、 3维卷积与转置卷积（可以简单理解为卷积操作的逆操作），但它们的使用方法比较相似，都可以从torch.nn模块中调用，需要调用的…...

编程日记 2025/5/11 5:22:45

【分布式架构理论3】分布式调用（1）：负载均衡

文章目录零、三种不同的负载均衡一、常见行业负载均衡方案1. 电商与互联网服务2. 金融与支付系统3. 云计算与分布式存储二、负载均衡策略概述1. 无状态负载均衡（强调公平性）2. 有状态的负载均衡（强调正确性） 三、总结零、三种…...

编程日记 2025/5/12 14:46:11

QT 5.15.2 开发地图ArcGIS 100.15.6（ArcGIS Runtime SDK for Qt）

QT 5.15.2ArcGIS下载 Downloads | ArcGIS Runtime API for Qt | Esri Developer ArcGIS安装（略）参考 Display a map | ArcGIS Maps SDK for Qt | Esri Developer QT新建工程步骤1 步骤2 步骤3 步骤4（选择Topographic不需要KEY) 步骤5&a…...

编程日记 2025/5/13 1:13:57

细读 React | React Router 路由切换原理

2022 北京冬奥会开幕式此前一直在疑惑，明明 pushState()、replaceState() 不触发 popstate 事件，可为什么 React Router 还能挂载对应路由的组件呢？ 翻了一下 history.js 源码，终于知道原因了。源码假设项目路由设计如下&#…...

编程日记 2025/5/12 13:38:35

kubernetes学习-Helm 包管理器（十二）

一、Helm解释 Helm：Kubernetes 的软件包管理器 Helm 被誉为查找、分享及使用 Kubernetes 软件组件的最佳途径。作为 Kubernetes 包的管理工具，Helm 专注于管理名为 chart 的软件包。以下是 Helm 所具备的核心功能： 创建新 chart&#xff1…...

编程日记 2025/5/14 12:25:03

PbootCMS最新代码注入漏洞（CNVD-2025-01710、CVE-2024-12789）

PbootCMS是一套高效、简洁、强悍的可免费商用的CMS源码，使用PHPMySQL开发，能够满足各类企业网站开发建设的需要。国家信息安全漏洞共享平台于2025-01-14公布该程序存在代码注入漏洞。漏洞编号：CNVD-2025-01710、CVE-2024-12789 影响产品…...

编程日记 2025/5/15 4:24:53

网络安全与AI：数字经济发展双引擎

在2025年年初，一场科技攻防战引发了全球关注。国产人工智能DeepSeek的爆火，伴随着大规模的网络攻击事件，将网络安全的重要性推上了风口浪尖。在此背景下，我们计划探讨网络安全与人工智能如何为数字经济发展提供强大动力。网络安…...

编程日记 2025/5/12 17:53:28

【DeepSeek × Postman】请求回复

新建一个集合在 Postman 中创建一个测试集合 DeepSeek API Test，并创建一个关联的测试环境 DeepSeek API Env，同时定义两个变量 base_url 和 api_key 的步骤如下： 1. 创建测试集合 DeepSeek API Test 打开 Postman。点击左侧导航栏中的 Co…...

编程日记 2025/5/13 18:39:25

如何将网站提交百度收录完整SEO教程

百度收录是中文网站获取流量的重要渠道。本文以我的网站，www.mnxz.fun（当然现在没啥流量） 为例，详细讲解从提交收录到自动化维护的全流程。一、百度收录提交方法 1. 验证网站所有权 1、登录百度搜索资源平台 2、选择「用户中心…...

编程日记 2025/5/12 21:36:59

【unity实战】实现摄像机跟随效果

考虑到每个人基础可能不一样，且并不是所有人都有同时做2D、3D开发的需求，所以我把【零基础入门unity游戏开发】分为成了C#篇、unity通用篇、unity3D篇、unity2D篇。【C#篇】：主要讲解C#的基础语法，包括变量、数据类型、运算符、流程控制、面向对象等，适合没有编程基础的…...

编程日记 2025/5/13 18:39:20

使用Hexo部署NexT主体网站

一.使用git提交文件参考： 从零开始搭建个人博客（超详细） - 知乎致谢！ 第一种：本地没有 git 仓库直接将远程仓库 clone 到本地；将文件添加并 commit 到本地仓库；将本地仓库的内容push到远程仓…...

编程日记 2025/5/13 18:39:18

使用 AlexNet 实现图片分类 | PyTorch 深度学习实战

前一篇文章，CNN 卷积神经网络处理图片任务 | PyTorch 深度学习实战本系列文章 GitHub Repo: https://github.com/hailiang-wang/pytorch-get-started 本篇文章内容来自于强化学习必修课：引领人工智能新时代【梗直哥瞿炜】使用 AlexNet 实现图片分类…...

编程日记 2025/5/13 18:39:16

ES6 Proxy 用法总结以及 Object.defineProperty用法区别

Proxy 是 ES6 引入的一种强大的拦截机制，用于定义对象的基本操作（如读取、赋值、删除等）的自定义行为。相较于 Object.defineProperty，Proxy 提供了更灵活、全面的拦截能力。 1. Proxy 语法 const proxy new Proxy(target, hand…...

编程日记 2025/5/16 17:29:09

初次体验Tauri和Sycamore (2)

编程日记 2025/5/13 18:39:12

Qt - 地图相关 —— 2、Qt调用百度在线地图功能示例全集，包含线路规划、地铁线路查询等（附源码）

效果：由于录制软件导致exe显示不正常，实际运行没有任何问题。作者其他相关文章链接: Qt - 地图相关 —— 1、加载百度在线地图（附源码）...

编程日记 2025/5/13 16:31:00

ffmpeg基本用法

一、用法 ffmpeg [options] [[infile options] -i infile]... {[outfile options] outfile}... 说明： global options：全局选项，应用于整个 FFmpeg 进程，它们通常不受输入或输出部分的限制。 infile options：输入选…...

编程日记 2025/5/13 18:39:10

redis底层数据结构——链表

文章目录定义内部实现总结定义链表提供了高效的节点重排能力，以及顺序性的节点访间方式，并且可以通过增删节点来灵活地调整链表的长度。作为一种常用数据结构，链表内置在很多高级的编程语言里面，因为Redis使用的C语言并没有…...

编程日记 2025/5/11 5:22:32

Repo命令使用

repo 命令与 git 类似，但它主要用于管理多个 Git 仓库的操作。以下是等效的 repo 命令： 1. 获取新仓库代码克隆仓库 repo init -u <manifest_url> -b <branch_name> repo sync repo init：初始化 repo，指定远程清单…...

编程日记 2025/5/11 5:22:29

React 高级教程

编程日记 2025/5/14 20:49:02

Linux: ASoC 声卡硬件参数的设置过程简析

文章目录 1. 前言2. ASoC 声卡设备硬件参数2.1 将 DAI、Machine 平台的硬件参数添加到声卡2.2 打开 PCM 流时将声卡硬件参数配置到 PCM 流2.3 应用程序对 PCM 流参数进行修改调整 1. 前言限于作者能力水平，本文可能存在谬误，因此而给读者带来的损失&am…...

编程日记 2025/5/15 14:57:30

网络基础知识与配置

目录网络基础知识 （一）网络的概念 （二）网络协议 （三）网络拓扑结构 （四）IP地址和子网掩码显示和配置网络接口 （一）在Windows系统中 （二&a…...

编程日记 2025/5/14 20:45:05

【STM32】ADC|多通道ADC采集

本次实现的是ADC实现数字信号与模拟信号的转化，数字信号时不连续的，模拟信号是连续的。 1.ADC转化的原理模拟-数字转换技术使用的是逐次逼近法，使用二分比较的方法来确定电压值当单片机对应的参考电压为3.3v时，0~ 3.3v(模拟信…...

编程日记 2025/5/16 15:15:34

centos 7 关于引用stdatomic.h的问题

问题：/tmp/tmp4usxmdso/main.c:6:23: fatal error: stdatomic.h: No such file or directory #include <stdatomic.h> 解决步骤： 1.这个错误是因为缺少C编译器的标准原子操作头文件 stdatomic.h。在Linux系统中，我们需要安装开发工具…...

编程日记 2025/5/12 17:54:25

用语言模型探索语音风格空间：无需情感标签的情感TTS

用语言模型探索语音风格空间：无需情感标签的情感TTS 原文：Exploring speech style spaces with language models: Emotional TTS without emotion labels 今天我们要说的是一种无需情感标签的情感TTS。提出了一个基于FastSpeech2的E-TTS框架&#xff0…...

编程日记 2025/5/14 21:14:33

将Excel中的图片保存下载并导出

目录效果演示注意事项核心代码有需要将excel中的图片解析出来保存到本地的小伙子们看过来！！！ 效果演示注意事项仅支持xlsx格式：此方法适用于Office 2007及以上版本的.xlsx文件，旧版.xls格式无法使用。图片名…...

编程日记 2025/5/16 8:21:37

2.11日学习总结

题目一 ： AC代码 #include <stdio.h> #include <stdlib.h>// 定义长整型 typedef long long ll;// 定义求最大值和最小值的宏函数 #define MAX(a, b) ((a) > (b) ? (a) : (b)) #define MIN(a, b) ((a) < (b) ? (a) : (b))// 定义数组和变量 ll…...

编程日记 2025/5/15 17:31:22

安川伺服控制器MP系列优势特点及行业应用

在工业自动化领域，运动控制器的性能直接决定了设备的精度、效率和可靠性。作为全球领先的运动控制品牌，安川电机伺服控制器凭借其卓越的技术优势和广泛的应用场景，正在为智能制造注入强劲动力！ MP3100：主板型运动控制…...

编程日记 2025/5/16 12:55:20

【腾讯地图】录入经纬度功能 - 支持地图选点

目录效果展示代码引入地图服务地址弹框中输入框 - 支持手动输入经纬度/地图选点按钮地图选点弹框组件当前文章 - 地图功能与 https://blog.csdn.net/m0_53562074/article/details/143677335 功能类似效果展示代码引入地图服务地址 public/index.html <!-- 互联网地图…...

编程日记 2025/5/12 14:46:10

Mybatis快速入门与核心知识总结

Mybatis 1. 实体类（Entity Class）1.1 实体类的定义1.2 简化编写1.2.1 Data1.2.2 AllArgsConstructor1.2.3 NoArgsConstructor 2. 创建 Mapper 接口2.1 Param2.2 #{} 占位符2.3 SQL 预编译 3. 配置 MyBatis XML 映射文件（可选）3.1 …...

编程日记 2025/5/14 9:45:37

RK3568平台开发系列讲解（调试篇）网卡队列均衡负载

🚀返回专栏总目录文章目录一、RPS 的介绍1. RPS 的工作原理2. RPS 配置3. 启用和调优 RPS4. RPS 优势二、下行测试iperf测试沉淀、分享、成长，让自己和他人都能有所收获！😄 RPS（Receive Packet Steering）是一种用于提高网络接收性能的技术，通常用于多核处理器系统中…...

编程日记 2025/5/14 17:57:44

Matlab机械手碰撞检测应用

本文包含三个部分： Matlab碰撞检测的实现URDF文件的制作机械手STL文件添加夹爪一.Matlab碰撞检测的实现首先上代码 %% 检测在结构环境中机器人是否与物体之间发生碰撞情况，如何避免？ % https://www.mathworks.com/help/robotics/ug/che…...

编程日记 2025/5/16 18:10:43

【前端】几种常见的跨域解决方案代理的概念

几种常见的跨域解决方案&代理的概念一、常见的跨域解决方案1. 服务端配置CORS（Cross-Origin Resource Sharing）：2. Nginx代理3. Vue CLI配置代理：4 .uni-app在manifest.json中配置代理来解决：5. 使用WebSocket通讯…...

编程日记 2025/5/11 5:21:58

服务器有多少线程?发起一个请求调用第三方服务，是新增加一个请求吗?如果服务器线程使用完了怎么办?

目录 1. 服务器有多少线程？（1）服务器类型（2）配置参数（3）硬件资源 2. 发起一个请求调用第三方服务，是新增加一个线程吗？（1）同步调用（2）异步调用（3）HTTP 客户端 3. 如果服务器线程使用完了怎么办？（1）请求被拒绝（2）性能下降（3）解决方案…...

编程日记 2025/5/11 5:21:55

【Spring AI】基于SpringAI+Vue3+ElementPlus的QA系统实现一

整理不易，请不要吝啬你的赞和收藏。 1. 前言这是 SpringAI 系列的第二篇文章，这篇文章将介绍如何基于 RAG 技术，使用 SpringAI Vue3 ElementPlus 实现一个 Q&A 系统。本文使用 deepseek 的 DeepSeek-V3 作为聊天模型，使用…...

编程日记 2025/5/16 13:25:03

前端快速生成接口方法

大家好，我是苏麟，今天聊一下OpenApi。官网 ： umijs/openapi - npm 安装命令 npm i --save-dev umijs/openapi 在根目录（项目目录下）创建文件 openapi.config.js import { generateService } from umijs/openapi// 自…...

编程日记 2025/5/16 14:58:11

【Qt 常用控件】多元素控件（QListWidget、QTabelWidgt、QTreeWidget）

**View和**Widget的区别？ **View的实现更底层，**Widget是基于**View封装实现的更易用的类型。 **View使用MVC结构 MVC是软件开发中经典的软件结构组织形式，软件设计模式。 M（model）模型。管理应用程序的核心数据和…...

编程日记 2025/5/11 22:06:52

java 读取sq3所有表数据到objectNode

1.实现效果：将sq3中所有表的所有字段读到objectNode 对象中，兼容后期表字段增删情况，数据组织形式如下图所示： 代码截图： 代码如下： package com.xxx.check.util;import java.sql.*; import java.util.Arr…...

编程日记 2025/5/12 22:06:47

react redux用法学习

参考资料： https://www.bilibili.com/video/BV1ZB4y1Z7o8 https://cn.redux.js.org/tutorials/essentials/part-5-async-logic AI工具：deepseek，通义灵码第一天安装相关依赖： 使用redux的中间件： npm i react-redu…...

编程日记 2025/5/13 18:39:05

C++20中的std::atomic_ref

一、std::atomic_ref 我们在学习C11后的原子操作时，都需要提前定义好std::atomic变量，然后才可以在后续的应用程序中进行使用。原子操作的优势在很多场合下优势非常明显，所以这也使得很多开发者越来习惯使用原子变量。但是，在实…...

编程日记 2025/5/13 18:39:03

encodeURI()，encodeURIComponent()区别

encodeURI()，encodeURIComponent()区别 encodeURI(): 对整个url(链接/网络链接)进行编码。对中文，完全编码。对英文不带空格则不会编码，带空格则会对空格编码。解码：decodeURI() 例如： let ChineseUrl "htt…...

编程日记 2025/5/13 13:27:03

Selenium：网页frame与多窗口处理

🍅 点击文末小卡片，免费获取软件测试全套资料，资料在手，涨薪更快一、多窗口处理 1.1、多窗口简介点击某些链接，会重新打开⼀个窗⼜，对于这种情况，想在新页⾯上操作，就得先切换窗…...

编程日记 2025/5/16 1:26:25

自动驾驶---如何打造一款属于自己的自动驾驶系统

在笔者的专栏《自动驾驶Planning决策规划》中，主要讲解了行车的相关知识，从Routing，到Behavior Planning，再到Motion Planning，以及最后的Control，笔者都做了相关介绍，其中主要包括算法在量产上…...

编程日记 2025/5/16 1:26:22

开源机器人+具身智能解决方案+AI

开源机器人、具身智能（Embodied Intelligence）以及AI技术的结合，可以为机器人领域带来全新的解决方案。以下是这一结合的可能方向和具体方案： 1. 开源机器人平台开源机器人平台为开发者提供了灵活的基础架构，可以在此基础上结合具身智能和AI技术。以下是一些常用的开源机…...

编程日记 2025/5/16 1:26:20

【web自动化】指定chromedriver以及chrome路径

selenium自动化，指定chromedriver，以及chrome路径对应这篇文章，可以点击查看，详情 from selenium import webdriverdef get_driver():# 获取配置对象option webdriver.ChromeOptions()option.add_experimental_option("de…...

编程日记 2025/5/16 1:26:18

高等代数笔记—线性变换

latex花体字母与花体数字 https://blog.csdn.net/weixin_39589455/article/details/133846783 https://blog.csdn.net/orz_include/article/details/123645710线性变换线性空间 V V V到自身的映射称为 V V V的一个变换，最基本的是线性变换。定义：变换…...

编程日记 2025/5/16 1:26:15

Kickstart自动化安装过程中自动选择较小的磁盘安装操作系统

Kickstart自动化安装过程中自动选择较小的磁盘安装操作系统需求在实际生成操作过程中，一般会遇到物理服务器存在多块盘的情况。安装过程中，磁盘的标签是随机分配的，并不是空间较小的盘，就会使用较小的磁盘标签而需求往往需要…...

编程日记 2025/5/15 3:21:04

2024BaseCTF_week4_web上

继续！冲冲冲目录圣钥之战1.0 nodejs 原型原型链原型链污染回到题目 flag直接读取不就行了？ 圣钥之战1.0 from flask import Flask,request import jsonapp Flask(__name__)def merge(src, dst):for k, v in src.items():if hasattr(dst, __geti…...

编程日记 2025/5/16 1:26:10

文章目录

一、dp

1.1 题意理解

1.2 整体思路

1.3 具体思路

1.4 代码

二、多语言解法

相关文章：