# Max Sum

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

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

Author

Ignatius.L

``` 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int main()
5 {
6     int n,j,i,num,a,ans,maxc,posst,posen,temp;
7       scanf("%d",&n);
8     for(i=1;i<=n;i++)
9     {
10         scanf("%d",&num);
11         maxc=0;
12         posst=posen=1;
13         ans=-0x3f3f3f3f ;
14         temp=0;
15      for(j=1;j<=num;j++)
16      {
17        scanf("%d",&a);
18         maxc+=a;
19        if(ans<maxc)
20         {
21           ans=maxc;
22           posen=j;
23           posst=temp+1;
24         }
25        if(maxc<0)
26        {
27         maxc=0;
28         temp=j;
29        }
30     }
31      printf("Case %d:\n%d %d %d\n",i,ans,posst,posen);
32      if(i!=n)  putchar(10);
33     }
34     return 0;
35 }```

0 条评论

• ### hdu 3853LOOPS (概率DP)

LOOPS Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 125536/65536 K (J...

• ### poj-------Common Subsequence(poj 1458)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submiss...

• ### md5算法原理一窥（其一）

首先，需要了解的事，md5并不是传说中的加密算法，只是一种散列算法。其加密的算法并不是我们说所的那样固定不变，只是一种映射的关系。 所以解密MD5没有现...

• ### JMX in action第二篇

其实一看到Dynamic这个词就基本上确定了，就是反射那一套，不外乎属性获取，设定，方法调用等等,但是这个在使用中是至关重要的，因为现有系统如果都想把接...

• ### 通用最小曼哈顿网络问题的动态编程方法（CS DS）

我们研究广义最小曼哈顿网络（GMMN）问题：给定一个由欧几里得平面 中两个点配对组成的集合 ，要求我们找到一个最小长度的几何网络，该网络由轴对齐的线段...

• ### torch.optim

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 教你如何提审iOS马甲包不会遇到2.1大礼包或4.3正确姿势分享

App Store 搜索关键词 世界杯 或者 通过链接下载 皇冠Ьet365-世界杯体育赛事直播吧：https://itunes.apple.com/cn/ap...

• ### 通过将语义和统计技术结合来动态丰富网络主体(cs.CL)

翻译：伴随着语义网技术的发展，开始更多使用本体来存储和提取覆盖多个领域的信息。但是，很少有本体能够处理得当不断更新的语义信息日益增长的需求，亦或是针对专业领域用...

• ### 复杂倒谱对声源语音的因果-反因果分解（CS Sound）

在文献中，复杂倒谱已知用于线性分离因果分量和反因果分量。 依靠Z变换零点（ZZT）技术取得的进展，我们在这里研究了在大型数据库上使用复杂倒谱进行声门流量估计的可...

• ### HDUOJ----1003 Max Sum

Max Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...