【洛谷 P1115】最大子段和 题解(贪心算法)
最大子段和
题目描述
给出一个长度为 n n n 的序列 a a a,选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数,表示序列的长度 n n n。
第二行有 n n n 个整数,第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
7
2 -4 3 -1 2 -4 3
样例输出 #1
4
提示
样例 1 解释
选取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2},其和为 4 4 4。
数据规模与约定
- 对于 40 % 40\% 40% 的数据,保证 n ≤ 2 × 1 0 3 n \leq 2 \times 10^3 n≤2×103。
- 对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105, − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 −104≤ai≤104。
思路
在遍历数组a时,累加每个元素的值,并在每次更新ans时使用max函数选择当前最大的子段和。
同时,如果当前的子段和sum小于0,则说明当前的子段对后面的结果没有贡献,因此将sum重置为0,从下一个元素重新开始计算。
AC代码
#include <iostream>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;const int maxn = 2e5 + 5;int main()
{int n;int a[maxn];int sum, ans;cin >> n;sum = 0;for (int i = 0; i < n; i++){cin >> a[i];if (!i){ans = a[0];}sum += a[i];ans = max(ans, sum);if (sum < 0){sum = 0;}}cout << ans << endl;return 0;
}
相关文章:
【洛谷 P1115】最大子段和 题解(贪心算法)
最大子段和 题目描述 给出一个长度为 n n n 的序列 a a a,选出其中连续且非空的一段使得这段和最大。 输入格式 第一行是一个整数,表示序列的长度 n n n。 第二行有 n n n 个整数,第 i i i 个整数表示序列的第 i i i 个数字 a i …...

uni-app--》基于小程序开发的电商平台项目实战(一)
🏍️作者简介:大家好,我是亦世凡华、渴望知识储备自己的一名在校大学生 🛵个人主页:亦世凡华、 🛺系列专栏:uni-app 🚲座右铭:人生亦可燃烧,亦可腐败…...

入门人工智能 —— 学习一门编程语言 python 基础代码编写和运算符介绍(1)
入门人工智能 —— 学习一门编程语言 python(1) 入门流程1.安装pythonwindowslinux ubuntu 代码编写打印输出结果 基本加减法介绍基本运算符 随着人工智能技术的快速发展,越来越多的年轻人开始关注这个领域。作为入门者,学习人工智…...

【java安全】CommonsBeanUtils1
文章目录 【java安全】CommonsBeanUtils1前言Apache Commons BeanutilsBeanComparator如何调用BeanComparator#compare()方法?构造POC完整POC 调用链 【java安全】CommonsBeanUtils1 前言 在之前我们学习了java.util.PriorityQueue,它是java中的一个优…...

JVM优化(OOM,内存溢出),查看线程快照,堆内存情况等问题
1:堆大小 新生代 老年代,新生代 ( Young ) 与老年代 ( Old ) 的比例的值为 1:2 ( 该值可以通过参数 –XX:NewRatio 来指定 ) 2:-Xmn参数总是应当小于-Xmx参数,否则就会触发OOM错误 3:jvm优化与查看gc回收情况&#x…...

git 给分支添加描述
需求:分支多了不知道当前分支的用处可以使用git br用来描述 效果: 全局安装命令 npm i -g git-br 项目内使用 git br 给f-230825-4-zhou分支备注 git config branch.f-230825-4-zhou.description 用来开发第四迭代需求 再次git br查看效果...

SpringBoot+Vue 整合websocket实现简单聊天窗口
效果图 1 输入临时名字充当账号使用 2 进入聊天窗口 3 发送消息 (复制一个页面,输入其他名字,方便展示效果) 4 其他窗口效果 代码实现 后端SpringBoot项目,自行创建 pom依赖 <dependency><groupId…...

PCB layout在布线上的设计规范有哪些?
PCB Layout是一项技术活,也是经验活,良好的PCB Layout布线可帮助工程师确保最终的电路板性能、可靠性和制造质量,因此是很多电子工程师的学习重点,下面我们来盘点下PCB Layout关于布线的规范有哪些。 1、地管的引脚接地越短越好&a…...

喜报丨迪捷软件入选浙江省2023年省级产业数字化服务商
近日,根据《关于组织开展2023年度省级产业数字化服务商申报工作的通知》要求,省经信厅公布2023年省级产业数字化服务商名单,浙江迪捷软件科技有限公司榜上有名。 省级产业数字化服务商上榜名单的评选在企业申报、地方推荐、专家评审、综合评估…...
verilog写rom,采用端口排序顺序例化
verilog写rom,采用端口排序顺序例化 1,介绍rom,以及rom与ram的区别2,RTL设计模块、门级网表以及testbench测试模块2.1 RTL设计2.2 门级网表2.3 testbench3,波形输出1,介绍rom,以及rom与ram的区别 参考文献: 1, 转载-ROM、RAM存储器原理详解以及DRAM、SRAM、SDRAM 、FLA…...

基于SSM的共享客栈管理系统的设计与实现
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用JSP技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…...
全屏Activity弹出键盘不顶起布局
最近遇到的一个问题是全屏Activity中要求弹出键盘不顶起布局,首先windowSoftInputMode的取值是有多个的,在全屏场景下adjustPan是没有用的,需要使用adjustResize首先确保键盘不顶起布局。 android:windowSoftInputMode"stateHidden|adju…...
JAVA设计模式详解 解构设计模式思想 详细代码对比
JAVA设计模式详解 1 简单工厂模式 1 简单工厂模式 设计模式-01简单工厂模式详解 详细代码对比...
lintcode 567 · 最大得分 【动态规划 中等 】
题目 https://www.lintcode.com/problem/567 给定一个矩阵matrix, matrix[i][j]表示你到达第i行第j列可以得到的分数,现在你要用第0行任意一点出发,从每行里找到一个点进行跳跃,每次从(i,j)到(i1,k)跳跃需要消耗∣j−k∣的分数&…...
qml嵌入到QWidget的两种方式介绍
本文介绍qml页面嵌入到QWidget的两种方式,以及这两种方式的区别。 方式1 在 Qt 中,可以使用 QQuickWidget 将 QML 内容嵌入到基于 QWidget 的应用程序中。这是在旧的 QWidget-based 应用程序中逐渐引入 QML UI 的一种常见方式。 以下是如何使用 QQuickWidget 将 QML 内容嵌…...

Mysql数据库之常用SQL语句及事务学习总结
数据库介绍 几个常见的缩写: DB:数据库。全称:DataBase。DBMS:数据库管理系统。全称:DataBase Management System。DBS:数据库系统。全称:DataBase System。DBA:数据库管理员。全称…...

RuoYi若依管理系统最新版 基于SpringBoot的权限管理系统
RuoYi是一个后台管理系统,基于经典技术组合(Spring Boot、Apache Shiro、MyBatis、Thymeleaf)主要目的让开发者注重专注业务,降低技术难度,从而节省人力成本,缩短项目周期,提高软件安全质量。 本…...

html实现邮件模版布局-flex布局table布局-demo
邮件模版布局 flex - 布局简单方便 兼容性差 table - 优点 就是兼容性好,其他没有优点 注:使用图片需要png最好,使用svg图google邮箱会出现不能使用的情况 效果图 flex布局 <!DOCTYPE html> <html lang"en" xmlns:th&qu…...
CENTOS7安装redis在/home/pms/software路径下,并且将redis加入到systemctl中
要将/home/software/redis-stack-server-7.2.0-v0/service/redis.service添加到systemctl系统管理,你可以执行以下步骤: 创建软连接: sudo ln -s /home/software/redis-stack-server-7.2.0-v0/service/redis.service /etc/systemd/system/r…...
数据库笔记
数据库原理及应用 半期考:运筹学,概率论,数据库 文章目录 数据库原理及应用1.课程的考核2.数据库的运用3.数据库学什么? 第一章 绪论1.1数据库系统概述1.1.1基本概念1.1.2数据管理技术的生产和发展人工管理文件系统数据库系统 1.…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...