Max Sum
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
解题思路:刚开始用最笨的方法试了一下,暴力搜索,全部走一边,时间花太多
了,超时了,对此改进了搜索的方式,只要两个循环就搞定了,时间加快了,但是相
对于来说还不是最快的,还是会超时的,一个个向后面走,只要和大于Max的,就记
录的,代码如下:
- #include<iostream>
- usingnamespacestd;
- intmain()
- {
- intn;
- cin>>n;
- intpoint1,point2;
- intstep=1;
- while(n)
- {
- intmax=-99999;
- intm,data[100000];
- cin>>m;
- for(inti=1;i<=m;i++)
- cin>>data[i];
- for(i=1;i<=m;i++)
- {
- intsum=0;
- for(intj=i;j<m;j++)
- {
- sum+=data[j];
- if(sum>max)
- {
- max=sum;
- point1=i;
- point2=j;
- }
- }
- }
- if(step!=1)
- cout<<endl;
- cout<<"Case"<<step<<":"<<endl;
- cout<<max<<""<<point1<<""<<point2<<endl;
- step++;
- n--;
- }
- return0;
- }
交上去还是超时的,最近用到动态规划,对算法进行改进了,起始点还是从头开始的,
一直到后面搜索,一直和为小于零,起始点就从开始小于零的后一位开始并把sum改为
零,再搜索的过程中,一遇到大的数据就记录下来,把其计为起始点和终点的,这里
面主要考虑到,当你搜索到一个位置的,它的和不小于零的,那对于后面来说,加上
去还是会变大的,不会给变小的,所以要再搜索下去的,走一边就KO了。代码如下:
- #include<iostream>
- usingnamespacestd;
- #defineMin-999999
- intmain()
- {
- intdata[100000],start,end;
- intm;
- intstep=1;
- cin>>m;
- while(m--)
- {
- intn;
- cin>>n;
- for(inti=1;i<=n;i++)
- cin>>data[i];
- intmax=Min;
- intk=1;
- intsum=0;
- for(i=1;i<=n;i++)
- {
- sum=sum+data[i];
- if(sum>max)
- {
- max=sum;
- start=k;
- end=i;
- }
- if(sum<0)
- {
- sum=0;
- k=i+1;
- }
- }
- if(step!=1)
- cout<<endl;
- cout<<"Case"<<step<<":"<<endl;
- cout<<max<<""<<start<<""<<end<<endl;
- step++;
- }
- return0;
- }
分享到:
相关推荐
杭电oj1000题解题报告
这是杭电OJ上某些题的解题报告,后续还有上传很多!
杭电OJ题目分类的叙述,可以方便去学习去做。
杭州电子科技大学ACM教程PPT,刘春英老师。。。。。,别的不多说了,下了再看。。。。
杭电OJ 2028代码 the rosolve of the hdu 2028
杭电OJ(1000-1099) AC 代码
本资源主要提供了杭电oj题目分类和自测状况两大类 可实现随机选题等功能.
包含很多ACM题目的源代码,各种类型都有,贪心,递归,分治,动态规划,RMQ,SPFA,BellmanDFSBFS
杭电OJ部分威士忌的代码 杭电OJ部分威士忌的代码杭电OJ部分威士忌的代码
杭电oj上的一些疑问,适用于初学者,可以解答一些疑问 都是一些水题
杭电oj 1047习题
杭电oj分类
杭州电子科技大学 oj离线版
这是HDUOJ上面的140道题目的答案,其中大部分都是简单题,有些太简单的就没有收集进去,代码为C/C++,全都AC了的,其中有些有具体的说明是怎么做的,例如博弈论那些
杭电oj的离线版以及题目分类的文档 更加一目了然 方便选择适合的题目做 适合暂时上不了网的用于练习
课程资源 杭电OJ1000-1099答案 ,仅供参考...
本人搜集的资源,经本人亲测,可用性强!!!适合大家参考...
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip