当前位置: 首页 > 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.…...

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:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&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 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

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内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针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 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

前端调试HTTP状态码

1xx&#xff08;信息类状态码&#xff09; 这类状态码表示临时响应&#xff0c;需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分&#xff0c;客户端应继续发送剩余部分。 2xx&#xff08;成功类状态码&#xff09; 表示请求已成功被服务器接收、理解并处…...