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

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...

Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合

无论是python&#xff0c;或者java 的大型项目中&#xff0c;都会涉及到 自身平台微服务之间的相互调用&#xff0c;以及和第三发平台的 接口对接&#xff0c;那在python 中是怎么实现的呢&#xff1f; 在 Python Web 开发中&#xff0c;FastAPI 和 Django 是两个重要但定位不…...