【洛谷 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.…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟
2025年4月29日,在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上,可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞,强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...