HOJ 1003 Max Sum 解题报告

好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路:

首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记。具体实现可以参考代码。

需要注意的地方有:当数组所有值都小于零时,我们在此进行特别的处理,找出最小的负数和相应的下标,然后在输出时和非全负数组的结果分开。(第一次提交的时候,没有考虑到全负的情况,WA了一次)

#include <stdio.h>

int main()
{
	int n,num,i,c;
	int min1,min2,max,sum1,sum2,temp,flag;
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	scanf("%d",&n);
	for(c=1; c<=n; c++)
	{
		scanf("%d",&num);
		flag = sum1 = sum2 = 0;
		min1 = min2 = max  = 1;
		int m, s, f=0;
		for(i=1; i <= num; i++)
		{
			scanf("%d",&temp);
			if(temp >= 0)f=1;
			
			if(1 == i){
				m = temp;
				s = i;
			}		
			else if(0 == f && temp > m){
				m = temp;
				s = i;
			}
			
			if(flag)		//if sum2 < 0, then execute follow action. 
			{
				if(temp >= 0)
				{
					sum2 = temp;
					min2 = i;
					flag = 0;
				}
				else{
					continue;
				}
			}else{
				sum2 += temp;
			}
			
			if(sum2 >= sum1)
			{
				max = i;
				sum1 = sum2;
				min1 = min2;
				
			}
			else if(sum2 < 0)
			{
				flag = 1;
			}
		}
		printf("Case %d:\n",c);
		if(1 == f){
			printf("%d %d %d\n",sum1,min1,max);
		}
		else{
			printf("%d %d %d\n",m,s,s);
		}
		if(c < n)printf("\n");
	}
	
	return 0;
}




更多相关文章
  • Time Limit:1MS      Memory Limit:32768KB Description Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence ...
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1003 Max Sum Time Limit: 2/1 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submiss
  • http://acm.hdu.edu.cn/showproblem.php?pid=1003 给你一串数列,让你求出其中 一段连续的子数列 并且 该子数列所有数字之和最大,输出该子数列的和.起点与终点序号. 具体细节
  • 1 #include <stdio.h> 2 int main(){ 3 int i,t,j,n,x; 4 int start,end,temp,max,sum; 5 scanf("%d",&t); 6 for(i=
  • Max Sum Time Limit: 2/1 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 135262    Accepted Submission(s): 31311 Pro ...
  • 经典DP #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int I
  • 这一题目是要求连续子序列的最大和,所以在看到题目的一瞬间就想到的是把所有情况列举出来,再两个两个的比较,取最大的(即为更新最大值的意思),这样的思路很简单,但是会超时,时间复杂度为O(n^3),因为有三重for语句
  • HDU 1003 Max Sum  HDU 1231 最大连续子序列 (DP)
    Max Sum Time Limit: 2/1 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 154155    Accepted Submission(s): 35958 Prob ...
一周排行
  • 


    		    ThinkPad T510系列主要機型對比
    本表简单易懂,主要针对打算购买TP的用户 本文出自 "李晨光原创技术博客&quo ...
  • 摘要: 关于java的IO,我们很多人都停留在java原API的一些stream上面,那么在网络中提到的BIO.NIO.AIO等关键词,你是否明白这个词的含义,以及其基本的原理?   注:此文也是本搬砖者转自网络,觉
  • appium for mobile web 之使用 ChromeDriver
    之前研究了一段时间的appium for native app 相应的总结如下:     ...
  • #include <stdio.h> #include <string.h> int zhuanhuan(char str[20]) {     if(strcmp(str,"zer ...
  • 今天在论坛看见有人讨论 C 语言中 main 函数的写法,看到结论才知道 main 函数的正确写法. 被老谭酸菜坑了这么多年,还是记录下吧,或许以后某天不搞 .net,回去折腾 C 语言了. 写法1: 1 int m
  • 写 ExtJs 相关代码多了就会用 xtype 的体会,下面是 ExtJs 中各组件的 xtype 与组 件类的对应表.不包括 Ext.ux 命名空间中扩展的组件.其实在 Ext API 文档中有此 列表,在 API
  • 


    		    Linux學習之標准IO 管道 033_7
    默认输入为键盘,标准输出为显示器,错误输出为显示器 把标准输出和错误输出重定向到文件: c
  • Nofuser
    google搜索了好久,最终找到这个工具,可直接使用. 虽然脱后有很多无用代码,但关键代码 ...
  • var ddl = document.getElementById("DropDownList1"); alert(ddl.selectedIndex);//选择索引值 alert(ddl.opt ...
  • 1.什么是JavaBeans? JavaBeans是Java语言中可以重复使用的软件组件,它们是一种特殊的Java类,将很多的对象封装到了一个对象(bean)中.特点是 可序列化, 提供无参构造器, 提供getter