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

Max Sum

一、题目

Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample
Inputcopy Outputcopy
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Case 1:
14 1 4

Case 2:
7 1 6

二、分析

计算连续数列的最大和,使用贪心算法。
如果sum小于0了,下一段sum重新开始,更新左端点

#include<iostream>
using namespace std;
int main()
{int T;cin>>T;for(int k=1;k<=T;k++){int n;cin>>n;int a[n+2];for(int i=1;i<=n;i++) cin>>a[i];int dp[n+2]={0};int st=1;int ansl=-1,ansr=-1,mx=-1e9,sum=0;//mx往开到极小for(int i=1;i<=n;i++){sum+=a[i];if(sum>mx){mx=sum;ansl=st;ansr=i;}if(sum<0){sum=0;st=i+1;}}cout << "Case " << k << ":" << endl;cout << mx << " " << ansl << " " << ansr <<endl<<endl;}
}

相关文章:

Max Sum

一、题目 Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 (-1) 5 4 14. Input The first line of the input contains an integer T(1<T<…...

Field injection is not recommended

文章目录 1. 引言2. 不推荐使用Autowired的原因3. Spring提供了三种主要的依赖注入方式3.1. 构造函数注入&#xff08;Constructor Injection&#xff09;3.2. Setter方法注入&#xff08;Setter Injection&#xff09;3.3. 字段注入&#xff08;Field Injection&#xff09; 4…...

C#字符串占位符替换

using System;namespace myprog {class test{static void Main(string[] args){string str1 string.Format("{0}今年{1}岁&#xff0c;身高{2}cm&#xff0c;月收入{3}元&#xff1b;", "小李", 23, 177, 5000);Console.WriteLine(str1);Console.ReadKey(…...

ChatGPT等人工智能编写文章的内容今后将成为常态

BuzzFeed股价上涨200%可能标志着“转向人工智能”媒体趋势的开始。 周四&#xff0c;一份内部备忘录被华尔街日报透露BuzzFeed正计划使用ChatGPT聊天机器人-风格文本合成技术来自OpenAI&#xff0c;用于创建个性化盘问和将来可能的其他内容。消息传出后&#xff0c;BuzzFeed的…...

【Sklearn】基于梯度提升树算法的数据分类预测(Excel可直接替换数据)

【Sklearn】基于梯度提升树算法的数据分类预测(Excel可直接替换数据) 1.模型原理2.模型参数3.文件结构4.Excel数据5.下载地址6.完整代码7.运行结果1.模型原理 梯度提升树(Gradient Boosting Trees)是一种集成学习方法,用于解决分类和回归问题。它通过将多个弱学习器(通常…...

什么叫做云计算?

相信大多数人对云计算或者是云服务的认识还停留在仅仅听过这个名词&#xff0c;但是对其真正的定义或者意义还不甚了解的层面。甚至有些技术人员&#xff0c;如果日常的业务不涉及到云服务&#xff0c;可能对其也只是一知半解的程度。首先云计算准确的讲只是云服务中的一部分&a…...

深度学习Batch Normalization

批标准化&#xff08;Batch Normalization&#xff0c;简称BN&#xff09;是一种用于深度神经网络的技术&#xff0c;它的主要目的是解决深度学习模型训练过程中的内部协变量偏移问题。简单来说&#xff0c;当我们在训练深度神经网络时&#xff0c;每一层的输入分布都可能会随着…...

el-table实现懒加载(el-table-infinite-scroll)

2023.8.15今天我学习了用el-table对大量的数据进行懒加载。 效果如下&#xff1a; 1.首先安装&#xff1a; npm install --save el-table-infinite-scroll2 2.全局引入&#xff1a; import ElTableInfiniteScroll from "el-table-infinite-scroll";// 懒加载 V…...

vueRouter回顾

关于vueRouter的两种路由模式 “history” 模式使用正常的 URL 格式&#xff0c;例如 https://example.com/path。“hash” 模式将路由信息添加到 URL 的哈希部分&#xff08;#&#xff09;后面&#xff0c;例如 https://example.com/#/path。 1、history模式&#xff1a;没有…...

大规模无人机集群算法flocking(蜂群)

matlab2016b正常运行...

【第三阶段】kotlin语言的split

const val INFO"kotlin,java,c,c#" fun main() {//list自动类型推断成listList<String>val listINFO.split(",")//直接输出list集合&#xff0c;不解构println("直接输出list的集合元素&#xff1a;$list")//类比c有解构&#xff0c;ktoli…...

机器学习笔记值优化算法(十四)梯度下降法在凸函数上的收敛性

机器学习笔记之优化算法——梯度下降法在凸函数上的收敛性 引言回顾&#xff1a;收敛速度&#xff1a;次线性收敛二次上界引理 梯度下降法在凸函数上的收敛性收敛性定理介绍证明过程 引言 本节将介绍梯度下降法在凸函数上的收敛性。 回顾&#xff1a; 收敛速度&#xff1a;次…...

iphone拷贝照片中间带E自动去重软件,以及java程序如何打包成jar和exe

文章目录 一、前提二、问题描述三、原始处理方式四、程序处理4.1 java程序如何打包exe4.1.1 首先打包jar4.1.2 开始生成exe4.1.3 软件使用方式 4.2 更换图标4.2.1 更换swing的打包jar图标4.2.2 更换exe图标 4.3 如何使生成的exe在没有java环境的电脑上运行4.3.1 Inno Setup打包…...

不同分类器对数据的处理

"""基于鸢尾花的不同分类器的效果比对:step1&#xff1a;准备数据&#xff1b;提取数据的特征向量X,Y将Y数据采用LabelEncoder转化为数值型数据;step2:将提取的特征向量X,Y进行拆分(训练集与测试集)step3:构建不同分类器并设置参数&#xff0c;例如&#xff1a;…...

十面骰子、

十面骰子(一): v 有一个十面的骰子&#xff0c;每一面分别为1-10&#xff0c;不断投掷骰子&#xff0c;投10000次&#xff0c;统计每一面1-10出现的次数或概率. v 提示&#xff1a;可用rand()产生1-10之间的随机数&#xff0c;再统计1-10出现的机会&#xff0c;存放于数组里,…...

IDE的下载和使用

IDE 文章目录 IDEJETBRAIN JETBRAIN 官网下载对应的ide 激活方式 dxm的电脑已经把这个脚本下载下来了&#xff0c;脚本是macjihuo 以后就不用买了...

华为OD机试真题【字母组合】

1、题目描述 【字母组合】 数字0、1、2、3、4、5、6、7、8、9分别关联 a~z 26个英文字母。 0 关联 “a”,”b”,”c” 1 关联 “d”,”e”,”f” 2 关联 “g”,”h”,”i” 3 关联 “j”,”k”,”l” 4 关联 “m”,”n”,”o” 5 关联 “p”,”q”,”r” 6 关联 “s”,”t” 7…...

Midjourney Prompt 提示词速查表 v5.2

Midjourney 最新的版本更新正不断推出令人兴奋的新功能。这虽然不断扩展了我们的AI绘图工具箱&#xff0c;但有时也会让我们难以掌握所有实际可以使用的功能和参数。 针对此问题, 小编整理了 "Midjourney Prompt 提示词速查表"&#xff0c;这是一个非常方便的 Midjo…...

自动驾驶——驶向未来的革命性技术

自动驾驶——驶向未来的革命性技术 自动驾驶的组件自动驾驶的优势自动驾驶的应用自动驾驶的未来中国的自动驾驶 自动驾驶是一种技术&#xff0c;它允许车辆在没有人类驾驶员的情况下自主地进行行驶。它利用各种传感器、计算机视觉、人工智能和机器学习算法来感知和理解周围环境…...

PAT (Advanced Level) 甲级 1004 Counting Leaves

点此查看所有题目集 A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child. Input Specification: Each input file contains one test case. Each case starts with a line containing 0<N<100, …...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...