HDU Max Sum

2017-11-15 929

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

Max Sum

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 191 Accepted Submission(s): 98

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 <iostream>
using namespace std;
int main()
{
    int T,N,max,sum,start,end,temp,t;
    cin>>T;
    int h = T;
    while(T--)
    {
        sum = 0;
        start = 1;
        end = 1;
        temp = 1;
        max = -1001;
        cin>>N;
       for(int i = 1; i <= N; i++)
       {
            cin>>t;
            sum +=t;
            if(sum>max)
            {
                max = sum;
                end = i;
                start = temp;
            }
            if(sum<0)
            {
                sum = 0;
                temp = i+1;
            }
       }
       if(T!=0)
       cout<<"Case "<<h-T<<":"<<endl<<max<<" "
       <<start<<" "<<end<<endl<<endl;
       else cout<<"Case "<<h-T<<":"<<endl<<max
       <<" "<<start<<" "<<end<<endl;
    }
    return 0;
}

本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/archive/2011/08/03/2125824.html，如需转载请自行联系原作者

文章标签：

Java

HDU Max Sum

Max Sum

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

HDU Max Sum

Max Sum

热门文章

最新文章

相关电子书