HDU 1003 Max Sum 最大子列和 | 在线处理算法_12 26 25的博客-程序员宅基地

技术标签: 算法  ACM  

在线处理

 

  • 定义: 在线 的意思是指每输入一个数据就进行 即是处理 ,在任何一个地方终止输入,算法都能能正确给出当前解

  • 特点:数据只需一次扫描,便可给出结果,无需在主机内存进行存储;并且在任何时刻,此算法都能根据输入给出正确结果。
  • 此算法非常高效,时间复杂度仅为0(N)

 

 


例题: HDU 1003 Max Sum 

Max Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 299181    Accepted Submission(s): 71008


 

Problem Description

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 Input

 

2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5

 

 

Sample Output

 

Case 1: 14 1 4 Case 2: 7 1 6

 

 

#include <stdio.h>
 
int main(){
	int t, n, maxLeft, maxRight, maxSum, temp;
	int thisLeft, thisSum;
	scanf("%d", &t);
	for(int id = 1; id <= t; ++id){
		scanf("%d", &n);
		scanf("%d", &maxSum);
		thisLeft = maxLeft = maxRight =  0;
		thisSum = maxSum;
		if(thisSum < 0){ thisSum = 0; thisLeft = 1; }
		for(int i = 1; i < n; ++i){
			scanf("%d", &temp);
			thisSum += temp;
			if(thisSum > maxSum){
				maxSum = thisSum;
				maxLeft = thisLeft;
				maxRight = i;
			}
			if(thisSum < 0){
				thisLeft = i + 1;
				thisSum = 0;
			}
		}
		printf("Case %d:\n%d %d %d\n", id, maxSum, maxLeft + 1, maxRight + 1);
		if(id != t) printf("\n");
	}
	return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41523096/article/details/83032516

智能推荐

CNN+LSTM+CTC_ShenLiang2025的博客-程序员宅基地_cnn_lstm_ctc

需求:调研CNN+LSTM+CTC的实现解决方案; 参考github实现示例代码:#!/usr/bin/env python2# -*- coding: utf-8 -*-&quot;&quot;&quot;tf CNN+LSTM+CTC 训练识别不定长数字字符图片@author: pengyuanjie&quot;&quot;&quot;from com.shenl.ocrTensorflowCnn.genIDCard import *...

常用评测网站合集_weixin_30458043的博客-程序员宅基地

洛谷luogu.orglojloj.acpojpoj.orgbzojlydsy.comhduacm.hdu.edu.cn转载于:https://www.cnblogs.com/darlingroot/p/11269162.html

Linux端口可以ping通但是telnet不通的原因_久安sweet的博客-程序员宅基地_linux端口telnet不通

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。本文链接:https://blog.csdn.net/Wan_Guo_Shi/article/details/78789092昨天应同学的要求在自己公司的云平台找了一台云主机上部署了分布式文件系统 FastDFS,安装经过比较顺利,但是在启动服务的时候出问题了,追踪器Tracker ...

Bellman_Ford最短路径算法_Muyan_Donny的博客-程序员宅基地

该算法可以说很简单,对每个节点维护两个信息,一个是源节点到该节点的距离,另一个是到该节点的前一个节点。也即前驱。假设当前用距离表A来保存所有点的这两个信息。假设有n个节点算法分为三步步走。第一步初始化A,A中所有距离均为无穷大,且前驱为空第二步,计算距离。对图中的每条边(u,v,w)都进行relax操作。其意义是,测试是否可以对从源节点s到v的最短路径进行改善。方法是:利用A中维护从源节点到任意节...

python调用可执行文件的方法_老笨妞的博客-程序员宅基地_python调用可执行文件

最近要用到python调用C程序,因此,看了一下python调用别的程序的方法。大致来说,python调用C/C++有两种方式,一种是调用C编译的动态链接库,即so文件,一种是调用C生成的可执行文件。具体用哪种根据应用场景来定。        python调用可执行文件,事实上是在python中执行原本在命令行中执行的命令。        具体方法:   (1). 写c++程序,并带有

随便推点

xss原理、攻击方式与防御_weixin_30851867的博客-程序员宅基地

xss原理:xss叫跨站脚本攻击,是Web程序中常见的漏洞只用于客户端的攻击方式,其原理是攻击者向有XSS漏洞的网站中输入(传入)恶意的HTML代码,当其它用户浏览该网站时,这段HTML代码会自动执行,从而达到攻击的目的。如,盗取用户Cookie、破坏页面结构、重定向到其它网站等。所以做网站的时候要明白一个道理:用户的输入是不可信的,所有可输入的地方都要进行数据进行处理才能杜绝xss攻击;...

编译原理学习笔记04——(孙悟空学72变之菩提老祖的阴谋—可怕的左递归)——2014_1_18_oldbeginner的博客-程序员宅基地

看左递归的时候,都是一个公式公式的,一个比一个抽象。看美剧的时候,遇到这种情况就会说,speaking English,翻译成中文:说点人话好不好。后来发现用从上而下的方法分析左递归,即对字符串进行分析时,指针是从左向右移动的,左递归的特点最左边就是非终结符,除非最左边生成终结符,否则指针怎么都无法指向终结符。但是非终结符生成终结符前,变化了多少次,是不知道的,通过尝试法,则会有大量回溯。

Tensorflow GPU训练过程中遇到的问题总结_szfhy的博客-程序员宅基地

错误类型:CUDA_ERROE_OUT_OF_MEMORYGPU的全部memory资源不能全部都申请,可以通过修改参数来解决:在session定义前增加config = tf.ConfigProto(allow_soft_placement=True)#最多占gpu资源的70%gpu_options = tf.GPUOptions(per_process_gpu_memory_fraction=0...

FZU 1571 排列的字典序问题_红烧春鸽的博客-程序员宅基地

Descriptionn个元素{1,2,...,n}有n!个不同的排列。将这n!个排列按字典序排列并编号为0,1,...,n!-1。每个排列的编号为其字典序值。例如,当n=3时,6个不同排列的字典序值如下:字典序值012345排列123132213231312321给定n,以及n个元素{1,

亿能bms上位机_BMS_CAN 基于USBCAN的BMS上位机软件,VC CSharp C#编程 238万源代码下载- www.pudn.com..._weixin_39976251的博客-程序员宅基地

文件名称: BMS_CAN下载 收藏√ [5 4 3 2 1]开发工具: Visual C++文件大小: 1079 KB上传时间: 2015-05-06下载次数: 1提 供 者: 龚先生详细说明:基于USBCAN的BMS上位机软件,VC-The BMS USBCAN based PC software文件列表(点击判断是否您需要的文件,如果是垃圾请在下面评价投诉):上位机........

android版本 6手机版下载,安卓投屏-安卓投屏下载 v8.5.1免费版--pc6下载站_美间的博客-程序员宅基地

安卓投屏是基于GitHub上的scrcpy项目二次开发,通过对接scrcpyapi接口,实现检测设备是否开启投屏窗口、一键全屏显示等功能,适用安卓平板、安卓手机、支持adb调试的机顶盒都可以通过有线或者无线连接投屏到PC上。安卓投屏是基于GitHub上的scrcpy项目二次开发,通过对接scrcpy api接口,实现检测设备是否开启投屏窗口、一键全屏显示等功能,适用安卓平板、安卓手机、支持adb调...