2014
03-23

# Max Sum II

Given a sequence a[1],a[2],a[3]……a[n], you can cut the sequence into one or more consecutive sub-sequences as you want, for example, you can cut them into (a[1]…a[j]), (a[k]…a[l]), (a[m]…a[n]),1≤j<k≤l<m≤n. Your job is to make the maximum sum using the least number of consecutive sub-sequences. For example, given (6,-1，0, -2, 3), the max sum in this sequence is 9, the number of sub-sequences is 2 not 3, they are(6), (3).

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<=1000000), then N integers followed(all the integers are between -1000 and 1000).

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<=1000000), then N integers followed(all the integers are between -1000 and 1000).

2
2 6 -5
5 6 -1 0 -2 3

Case 1:
1 6

Case 2:
2 9

/*
hdu 3421 Max Sum II 读不懂题的伤不起啊

*/

#include<stdio.h>
__int64 he;
int main()
{
int t,n,i,ret,qian,j,dang;
scanf("%d",&t);
for(i=1;i<=t;)
{
he=0;
scanf("%d",&n);
qian=-1;
ret=0;
int ji=0;
for(j=1;j<=n;j++)
{
scanf("%d",&dang);
if(dang>0) he+=dang;
if(ji)
{
if(dang<0)
{
ji=0;
}
}else
{
if(dang==0)
{

}else if(dang>0)
{
ji=1;
ret++;
}
}
}
if(i!=1)
printf("\n");
printf("Case %d:\n",i++);
printf("%d %I64d\n",ret,he);
}
return 0;
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。