洛谷 P1115 最大子段和(前缀和详解)c++

题目链接:P1115 最大子段和 - 洛谷

1.题目分析

2.算法原理

解法:利用前缀和
思考:如何求出以a[i]为结尾的所有子区间中最大的子段和


假设 i 等于5,以 a[ i ] 为结尾的区间一共是五段(黑色线条部分),在这5段中找出最大的子段和,或者针对 i = 4 也能找到最大的子段和,i 等于1,2,3都能找到最大的子段和的话,在这所有情况里面取一个max就是最终结果了 

先解决眼前的问题,如何找出以 a [ i ] 为结尾的最大子段和,只要能找到这一个,所有位置的最大子段和都能找出来,在所有情况下取一个最大值就可以了,当我想求黑色部分的时候,是拿所有区间的和减去红色部分,正好是 f [ i ](前缀和)- f [ x ](前面某一个区间的和),1 <= x <= i - 1,所以如何找出以 a [ i ] 为结尾的最大子段和,就是在找这个公式中所有计算的最大值,f [ i ] 是个定值,表示从1到 i 区间的和,f [ x ] 是变化的,如果想要减式的结果最大,那就要让减数最小就可以了,让整段区间的和,减去前面区间里最小的区间和,此时找到的就是最大的区间和

用 f [ i ] 减去 [1, i - 1] 中所有前缀和的最小值即可,假设现在 i 是 5,用1到 i 的区间和减去计算的前缀和中最小的值,就是以 i 为结尾的最大区间和了,再把下标6的位置求出来,7的位置求出来,在所有情况里面取一个最大值就可以了

如何快速找出 [1, i - 1] 中所有前缀和的最小值,一边计算 f [ i ] 的时候,一边更新前缀最小值,prevmin表示前缀最小值,假设计算下标5的前缀和的时候,prevmin表示1-4区间的前缀和最小值,计算完 f [ i ] 的时候,prevmin和 f [ i ] 取一个min,同时在赋值给prevmin,就可以在往后递推的过程中,计算 f [ i ] 的时候,prevmin里面就存着1-5区间里面前缀和的最小值,当计算下一个位置的前缀和的时候,prevmin记录着前面区间里面所有前缀和的最小值,计算完当前位置的时候,再对prevmin与当前位置的 f [ i ] 取个最小值就可以了,所以我们就可以在从前往后循环的过程中,搞一个变量计录一下前缀和的最小值就ok了

代码:

#include <iostream>
using namespace std;typedef long long LL;
const int N = 2e5 + 10;
int n;
LL f[N]; // 前缀和数组int main()
{cin >> n;for(int i = 1; i <= n; i++){LL x; cin >> x;f[i] = f[i - 1] + x;}LL ret = -1e20;LL prevmin = 0;for(int i = 1; i <= n; i++){ret = max(ret, f[i] - prevmin);prevmin = min(prevmin, f[i]);}cout << ret << endl;return 0;
}

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/35290.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JetBrains(全家桶: IDEA、WebStorm、GoLand、PyCharm) 2024.3+ 2025 版免费体验方案

JetBrains&#xff08;全家桶: IDEA、WebStorm、GoLand、PyCharm&#xff09; 2024.3 2025 版免费体验方案 前言 JetBrains IDE 是许多开发者的主力工具&#xff0c;但从 2024.02 版本起&#xff0c;JetBrains 调整了试用政策&#xff0c;新用户不再享有默认的 30 天免费试用…

【数据分析】数据筛选与访问行列元素3

访问元素 .loc属性可以通过传入index的值访问行数据。 .loc属性允许传入两个参数&#xff0c;分别是index的值和columns的值&#xff0c;参数间用“逗号”隔开&#xff0c;这样便可以访问数据中的元素。 1. 访问单个元素 访问单个元素比较简单&#xff0c;只需要通过它的in…

C++ std::list超详细指南:基础实践(手搓list)

目录 一.核心特性 1.双向循环链表结构 2.头文件&#xff1a;#include 3.时间复杂度 4.内存特性 二.构造函数 三.list iterator的使用 1.学习list iterator之前我们要知道iterator的区分 ​编辑 2.begin()end() 3.rbegin()rend() 四.list关键接口 1.empty() 2. size…

【免费】2004-2017年各地级市进出口总额数据

2004-2017年各地级市进出口总额数据 1、时间&#xff1a;2004-2017年 2、来源&#xff1a;城市年鉴 3、指标&#xff1a;进出口贸易总额 4、范围&#xff1a;286个地级市 5、指标说明&#xff1a;进出口总额是指一个国家在特定时期内&#xff08;通常为一年&#xff09;所…

谈谈 undefined 和 null

*** 补充 null 和 ‘’

【第15届蓝桥杯】软件赛CB组省赛

个人主页&#xff1a;Guiat 归属专栏&#xff1a;算法竞赛真题题解 文章目录 A. 握手问题&#xff08;填空题&#xff09;B. 小球反弹&#xff08;填空题&#xff09;C. 好数D. R格式E. 宝石组合F. 数字接龙G. 爬山H. 拔河 正文 总共8道题。 A. 握手问题&#xff08;填空题&…

【计算机视觉】工业表计读数(2)--表计检测

1. 简介 工业表计&#xff08;如压力表、电表、气表等&#xff09;在工控系统、能源管理等领域具有重要应用。然而&#xff0c;传统人工抄表不仅工作量大、效率低&#xff0c;而且容易产生数据误差。近年来&#xff0c;基于深度学习的目标检测方法在工业检测中展现出极大优势&…

提示词工程(Prompt Engineering)

https://www.bilibili.com/video/BV1PX9iYQEry 一、懂原理&#xff0c;要知道 为什么有的指令有效&#xff0c;有的指令无效为什么同样的指令有时有效&#xff0c;又是无效怎么提升指令有效的概率 大模型应用架构师想什么&#xff1f; 怎样能更准确&#xff1f;答&#xff1…

从Instagram到画廊:社交平台如何改变艺术家的展示方式

从Instagram到画廊&#xff1a;社交平台如何改变艺术家的展示方式 在数字时代&#xff0c;艺术家的展示方式正在经历一场革命。社交平台&#xff0c;尤其是Instagram&#xff0c;已经成为艺术家展示作品、与观众互动和建立品牌的重要渠道。本文将探讨社交平台如何改变艺术家的…

Typora 使用教程(标题,段落,字体,列表,区块,代码,脚注,插入图片,表格,目录)

标题 一个#是一级标题, 2个#是二级标题, 以此类推, 最多可达六级标题 示例 输入#号和标题后回车即可 注意: #和标题内容之间需要存在空格(一个或多个均可), 没有空格就会变成普通文字 标题快捷键 Ctrl数字 1-6 可以快速调成对应级别的标题 (选中文本/把光标放在标题上再按…

关于deepseek R1模型分布式推理效率分析

1、引言 DeepSeek R1 采用了混合专家&#xff08;Mixture of Experts&#xff0c;MoE&#xff09;架构&#xff0c;包含多个专家子网络&#xff0c;并通过一个门控机制动态地激活最相关的专家来处理特定的任务 。DeepSeek R1 总共有 6710 亿个参数&#xff0c;但在每个前向传播…

力扣hot100二刷——二叉树

第二次刷题不在idea写代码&#xff0c;而是直接在leetcode网站上写&#xff0c;“逼”自己掌握常用的函数。 标志掌握程度解释办法⭐Fully 完全掌握看到题目就有思路&#xff0c;编程也很流利⭐⭐Basically 基本掌握需要稍作思考&#xff0c;或者看到提示方法后能解答⭐⭐⭐Sl…

网络安全 --- 基于网络安全的 Linux 最敏感目录及文件利用指南

目录 基于网络安全的 Linux 最敏感目录及文件利用指南 Linux 中最敏感的目录及文件 1. /etc 2. /root 3. /var/log 4. /proc 5. /tmp 6. /home 7. /boot 8. /dev 如何利用这些敏感文件 你可能没想到的知识点 总结 Linux 中最敏感的目录及文件 1. /etc 存放内容&a…

深入浅出:Java实现斐波那契数列的七种武器与性能调优指南

​​​ 引言:当数学之美邂逅算法之力 斐波那契数列——这个诞生于13世纪的数学瑰宝,在计算机科学中焕发出新的生命力。作为递归与动态规划的经典案例,它不仅是算法入门的必修课,更是性能优化的试金石。本文将带您深入探索Java实现斐波那契数列的七种核心方法,并揭秘不同…

音视频入门基础:RTP专题(17)——音频的SDP媒体描述

一、引言 在《音视频入门基础&#xff1a;RTP专题&#xff08;3&#xff09;——SDP简介》中对SDP协议进行了简介&#xff0c;以H.264为例介绍了视频的SDP的媒体描述。本文对该文章进行补充&#xff0c;以AAC为例&#xff0c;讲述音频的SDP媒体描述。 二、文档下载 《RFC 364…

MyBatis-Plus防全表更新与删除插件BlockAttackInnerInterceptor

防全表更新与删除插件 BlockAttackInnerInterceptor 是 MyBatis-Plus 框架提供的一个安全插件&#xff0c;专门用于防止恶意的全表更新和删除操作。该插件通过拦截 update 和 delete 语句&#xff0c;确保这些操作不会无意中影响到整个数据表&#xff0c;从而保护数据的完整性…

嵌入式开发之STM32学习笔记day06

基于STM32F103C8T6的开发实践——从入门到精通01 1. 引言 STM32系列微控制器是STMicroelectronics推出的一款高性能、低功耗的32位微控制器&#xff0c;广泛应用于嵌入式系统中。STM32F103C8T6是其中非常受欢迎的一款&#xff0c;凭借其强大的性能、丰富的外设接口和低廉的价格…

TCP/IP 协议精讲-精华总结版本

序言 本文旨在介绍一下TCP/IP涉及得所有基础知识&#xff0c;为大家从宏观上俯瞰TCP/IP提供一个基石&#xff0c;文档属于《TCP/IP图解&#xff08;第五版&#xff09;》的精简版本。 专业术语 缩写 全称 WAN Wide area network广域网 LAN Local area network局域网 TC…

Ubuntu22.04虚拟机里安装Yolov8流程

1. 安装pytorch sudo apt install nvidia-cuda-toolkit nvcc --version # 官方适配地址&#xff1a;https://download.pytorch.org/whl/torch/import torch print(torch.__version__) print(torch.cuda.is_available())2. 安装环境 # cuDNN 安装&#xff1a;https://develop…

stm32第五天按键的基础知识

一&#xff1a;按键连接示意图 按键控制LED灯 软件设计流程 初始化系统 o 初始化GPIO外设时钟 o 初始化按键和LED的引脚 • 检测按键输入电平来控制LED灯 o SW2控制灯开 。 SW3控制灯关 1&#xff1a;key.c工程 #include"key.h" #include"stm32f10x.h"v…