文档章节

Max Sum 杭电 1003

聪聪lovely
 聪聪lovely
发布于 2016/07/02 19:04
字数 398
阅读 15
收藏 0

又是凌晨两三点,这也许就是程序员的诟病。当看到这道题的时候,脑袋里面出现的就是,动态规划,大家不要笑我。我也是个菜鸟,毕竟大家都是在不断地学习中。

题目的意思是给你一个数列,找到一个子数列,这个子数列的和是所有子数列中和最大的。

当然把数列的所有数都列出来肯定不现实。

黑黑,不知道正不正确,我是先从第一个数开始依次加到最后一个数,并且把每一次加的和存到对应的一个和数组中。这样得到了一个不间断的和的数列,但是这样显然还是不行,在加的时候你还得判断一下,当和小于零的时候,就得把起始位置,向后挪一个了。这样才能保证,每次求得的子序列的和是所有子序列当中和最小的。

懂不懂先不说,附上代码:

 

import java.math.BigDecimal;
import java.util.Scanner;
import java.util.Stack;

public class Main{
	
	public static void main(String []args){
		
		Scanner cin=new Scanner(System.in);
		
		int t=cin.nextInt();
		int [] num=new int[100000];
		int [] sum=new int[100000];
		
		for (int i=1; i<=t; i++){	
			
			int n=cin.nextInt(); 
			
			for (int j=0; j<n; j++){
				num[j]=cin.nextInt();
			}
			
			int su=0;
			int start=0;
			int end=0;
			
			for (int j=0; j<n; j++){
				sum[j]=0;
			}
			
			for (int j=0; j<n; j++){
				su+=num[j];
				sum[j]+=su;
				
				if (su<0) su=0;
			}
			
			for (int j=1; j<n; j++){
				if (sum[end]<sum[j]) end=j;
			}
			
			start=end;
			while (start>0&&sum[start-1]>=0){
				start--;
			}
			
			start++;
			end++;
			
			System.out.println("Case "+i+":");
			System.out.println(sum[end-1]+" "+start+" "+end);
			if (i<t) System.out.println();
		}
	}
}

 

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
聪聪lovely
粉丝 10
博文 29
码字总数 18342
作品 0
吉林
程序员
私信 提问
HDU - 1003 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......

Daybreaking
2018/07/29
0
0
Oracle面试题及答案整理

1、表:table1(FId,Fclass,Fscore),用最高效最简单的SQL列出各班成绩最高的列表,显示班级,成绩两个字段。 select fclass,max(fscore) from table1 group by fclass,fid 2、有一个表table1有...

zting科技
2017/10/17
0
0
linux 取随机数方法的五种方法

随机数方法 1、cat /proc/sys/kernel/random/uuid 75aae497-937b-4e4e-87e2-b1003f5a44f5 2、rand -base64 65 umdqq7PJ8K4a/j/uhlMEa6AHEhE9TXTdL3Pp4w5UqycSXuCk0OioenTDtIPv/TCTSdwmpcVg0......

yuelass
2017/04/24
0
0
几个算法题

1 在一个字符串中找到第一个只出现一次的字符,如输入abac,则输出b 本题看似很简单,开个长度为256的表,对每个字符hash计数就可以了,但很多人写的代码都存在bug,可能会发生越界访问。这是...

泳泳啊泳泳
2017/12/25
0
0
触发器-4

三、DML触发器 1.控制数据安全 案例01: /* 限制用户只能在工作时间8:00到17:00修改表apple中的数据 */ create or replace trigger tr_work_apple before insert or update or delete on ...

晨曦之光
2012/04/19
79
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 升级中的一些常见问题

升级的时候遇到了问题了吗? 如果你想尝试重新进行升级的话,你需要首先重新恢复老的备份。不要尝试再次对 Confluence 进行升级或者在升级失败后重新启动老的 Confluence。 在升级过程中的一...

honeymoose
今天
2
0
C++随笔(四)Nuget打包

首先把自己编译好的包全部准备到一个文件夹 像这样 接下来新建一个文本文档,后缀名叫.nuspec 填写内容 <?xml version="1.0"?><package xmlns="http://schemas.microsoft.com/packaging/201......

Pulsar-V
今天
2
0
再谈使用开源软件搭建数据分析平台

三年前,我写了这篇博客使用开源软件快速搭建数据分析平台, 当时收到了许多的反馈,有50个点赞和300+的收藏。到现在我还能收到一些关于dataplay2的问题。在过去的三年,开源社区和新技术的发...

naughty
今天
3
0
Python3的日期和时间

python 中处理日期时间数据通常使用datetime和time库 因为这两个库中的一些功能有些重复,所以,首先我们来比较一下这两个库的区别,这可以帮助我们在适当的情况下时候合适的库。 在Python文...

编程老陆
今天
2
0
分布式面试整理

并发和并行 并行是两个任务同时进行,而并发呢,则是一会做一个任务一会又切换做另一个任务。 临界区 临界区用来表示一种公共资源或者说是共享数据,可以被多个线程使用,但是每一次,只能有...

群星纪元
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部