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

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...