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. 构造函数注入(Constructor Injection)3.2. Setter方法注入(Setter Injection)3.3. 字段注入(Field Injection) 4…...
C#字符串占位符替换
using System;namespace myprog {class test{static void Main(string[] args){string str1 string.Format("{0}今年{1}岁,身高{2}cm,月收入{3}元;", "小李", 23, 177, 5000);Console.WriteLine(str1);Console.ReadKey(…...
ChatGPT等人工智能编写文章的内容今后将成为常态
BuzzFeed股价上涨200%可能标志着“转向人工智能”媒体趋势的开始。 周四,一份内部备忘录被华尔街日报透露BuzzFeed正计划使用ChatGPT聊天机器人-风格文本合成技术来自OpenAI,用于创建个性化盘问和将来可能的其他内容。消息传出后,BuzzFeed的…...
【Sklearn】基于梯度提升树算法的数据分类预测(Excel可直接替换数据)
【Sklearn】基于梯度提升树算法的数据分类预测(Excel可直接替换数据) 1.模型原理2.模型参数3.文件结构4.Excel数据5.下载地址6.完整代码7.运行结果1.模型原理 梯度提升树(Gradient Boosting Trees)是一种集成学习方法,用于解决分类和回归问题。它通过将多个弱学习器(通常…...
什么叫做云计算?
相信大多数人对云计算或者是云服务的认识还停留在仅仅听过这个名词,但是对其真正的定义或者意义还不甚了解的层面。甚至有些技术人员,如果日常的业务不涉及到云服务,可能对其也只是一知半解的程度。首先云计算准确的讲只是云服务中的一部分&a…...
深度学习Batch Normalization
批标准化(Batch Normalization,简称BN)是一种用于深度神经网络的技术,它的主要目的是解决深度学习模型训练过程中的内部协变量偏移问题。简单来说,当我们在训练深度神经网络时,每一层的输入分布都可能会随着…...
el-table实现懒加载(el-table-infinite-scroll)
2023.8.15今天我学习了用el-table对大量的数据进行懒加载。 效果如下: 1.首先安装: npm install --save el-table-infinite-scroll2 2.全局引入: import ElTableInfiniteScroll from "el-table-infinite-scroll";// 懒加载 V…...
vueRouter回顾
关于vueRouter的两种路由模式 “history” 模式使用正常的 URL 格式,例如 https://example.com/path。“hash” 模式将路由信息添加到 URL 的哈希部分(#)后面,例如 https://example.com/#/path。 1、history模式:没有…...
大规模无人机集群算法flocking(蜂群)
matlab2016b正常运行...
【第三阶段】kotlin语言的split
const val INFO"kotlin,java,c,c#" fun main() {//list自动类型推断成listList<String>val listINFO.split(",")//直接输出list集合,不解构println("直接输出list的集合元素:$list")//类比c有解构,ktoli…...
机器学习笔记值优化算法(十四)梯度下降法在凸函数上的收敛性
机器学习笔记之优化算法——梯度下降法在凸函数上的收敛性 引言回顾:收敛速度:次线性收敛二次上界引理 梯度下降法在凸函数上的收敛性收敛性定理介绍证明过程 引言 本节将介绍梯度下降法在凸函数上的收敛性。 回顾: 收敛速度:次…...
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:准备数据;提取数据的特征向量X,Y将Y数据采用LabelEncoder转化为数值型数据;step2:将提取的特征向量X,Y进行拆分(训练集与测试集)step3:构建不同分类器并设置参数,例如:…...
十面骰子、
十面骰子(一): v 有一个十面的骰子,每一面分别为1-10,不断投掷骰子,投10000次,统计每一面1-10出现的次数或概率. v 提示:可用rand()产生1-10之间的随机数,再统计1-10出现的机会,存放于数组里,…...
IDE的下载和使用
IDE 文章目录 IDEJETBRAIN JETBRAIN 官网下载对应的ide 激活方式 dxm的电脑已经把这个脚本下载下来了,脚本是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绘图工具箱,但有时也会让我们难以掌握所有实际可以使用的功能和参数。 针对此问题, 小编整理了 "Midjourney Prompt 提示词速查表",这是一个非常方便的 Midjo…...
自动驾驶——驶向未来的革命性技术
自动驾驶——驶向未来的革命性技术 自动驾驶的组件自动驾驶的优势自动驾驶的应用自动驾驶的未来中国的自动驾驶 自动驾驶是一种技术,它允许车辆在没有人类驾驶员的情况下自主地进行行驶。它利用各种传感器、计算机视觉、人工智能和机器学习算法来感知和理解周围环境…...
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, …...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
