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

【洛谷 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 n2×103
  • 对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1n2×105 − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 104ai104

思路

在遍历数组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&#xff0c;选出其中连续且非空的一段使得这段和最大。 输入格式 第一行是一个整数&#xff0c;表示序列的长度 n n n。 第二行有 n n n 个整数&#xff0c;第 i i i 个整数表示序列的第 i i i 个数字 a i …...

uni-app--》基于小程序开发的电商平台项目实战(一)

&#x1f3cd;️作者简介&#xff1a;大家好&#xff0c;我是亦世凡华、渴望知识储备自己的一名在校大学生 &#x1f6f5;个人主页&#xff1a;亦世凡华、 &#x1f6fa;系列专栏&#xff1a;uni-app &#x1f6b2;座右铭&#xff1a;人生亦可燃烧&#xff0c;亦可腐败&#xf…...

入门人工智能 —— 学习一门编程语言 python 基础代码编写和运算符介绍(1)

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

【java安全】CommonsBeanUtils1

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

JVM优化(OOM,内存溢出),查看线程快照,堆内存情况等问题

1&#xff1a;堆大小 新生代 老年代&#xff0c;新生代 ( Young ) 与老年代 ( Old ) 的比例的值为 1:2 ( 该值可以通过参数 –XX:NewRatio 来指定 ) 2&#xff1a;-Xmn参数总是应当小于-Xmx参数&#xff0c;否则就会触发OOM错误 3&#xff1a;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 发送消息 &#xff08;复制一个页面&#xff0c;输入其他名字&#xff0c;方便展示效果&#xff09; 4 其他窗口效果 代码实现 后端SpringBoot项目&#xff0c;自行创建 pom依赖 <dependency><groupId…...

PCB layout在布线上的设计规范有哪些?

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

喜报丨迪捷软件入选浙江省2023年省级产业数字化服务商

近日&#xff0c;根据《关于组织开展2023年度省级产业数字化服务商申报工作的通知》要求&#xff0c;省经信厅公布2023年省级产业数字化服务商名单&#xff0c;浙江迪捷软件科技有限公司榜上有名。 省级产业数字化服务商上榜名单的评选在企业申报、地方推荐、专家评审、综合评估…...

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的共享客栈管理系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…...

全屏Activity弹出键盘不顶起布局

最近遇到的一个问题是全屏Activity中要求弹出键盘不顶起布局&#xff0c;首先windowSoftInputMode的取值是有多个的&#xff0c;在全屏场景下adjustPan是没有用的&#xff0c;需要使用adjustResize首先确保键盘不顶起布局。 android:windowSoftInputMode"stateHidden|adju…...

JAVA设计模式详解 解构设计模式思想 详细代码对比

JAVA设计模式详解 1 简单工厂模式 1 简单工厂模式 设计模式-01简单工厂模式详解 详细代码对比...

lintcode 567 · 最大得分 【动态规划 中等 】

题目 https://www.lintcode.com/problem/567 给定一个矩阵matrix&#xff0c; matrix[i][j]表示你到达第i行第j列可以得到的分数&#xff0c;现在你要用第0行任意一点出发&#xff0c;从每行里找到一个点进行跳跃&#xff0c;每次从(i,j)到(i1,k)跳跃需要消耗∣j−k∣的分数&…...

qml嵌入到QWidget的两种方式介绍

本文介绍qml页面嵌入到QWidget的两种方式,以及这两种方式的区别。 方式1 在 Qt 中,可以使用 QQuickWidget 将 QML 内容嵌入到基于 QWidget 的应用程序中。这是在旧的 QWidget-based 应用程序中逐渐引入 QML UI 的一种常见方式。 以下是如何使用 QQuickWidget 将 QML 内容嵌…...

Mysql数据库之常用SQL语句及事务学习总结

数据库介绍 几个常见的缩写&#xff1a; DB&#xff1a;数据库。全称&#xff1a;DataBase。DBMS&#xff1a;数据库管理系统。全称&#xff1a;DataBase Management System。DBS&#xff1a;数据库系统。全称&#xff1a;DataBase System。DBA&#xff1a;数据库管理员。全称…...

RuoYi若依管理系统最新版 基于SpringBoot的权限管理系统

RuoYi是一个后台管理系统&#xff0c;基于经典技术组合&#xff08;Spring Boot、Apache Shiro、MyBatis、Thymeleaf&#xff09;主要目的让开发者注重专注业务&#xff0c;降低技术难度&#xff0c;从而节省人力成本&#xff0c;缩短项目周期&#xff0c;提高软件安全质量。 本…...

html实现邮件模版布局-flex布局table布局-demo

邮件模版布局 flex - 布局简单方便 兼容性差 table - 优点 就是兼容性好&#xff0c;其他没有优点 注&#xff1a;使用图片需要png最好&#xff0c;使用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系统管理&#xff0c;你可以执行以下步骤&#xff1a; 创建软连接&#xff1a; sudo ln -s /home/software/redis-stack-server-7.2.0-v0/service/redis.service /etc/systemd/system/r…...

数据库笔记

数据库原理及应用 半期考&#xff1a;运筹学&#xff0c;概率论&#xff0c;数据库 文章目录 数据库原理及应用1.课程的考核2.数据库的运用3.数据库学什么&#xff1f; 第一章 绪论1.1数据库系统概述1.1.1基本概念1.1.2数据管理技术的生产和发展人工管理文件系统数据库系统 1.…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤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 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...