HDU 1003
-
#include <iostream>
-
using namespace std;
-
int main()
-
{
-
int j,i,k,n,m,t;
-
int a[100002];
-
scanf("%d",&t);
-
for (j=1;j<=t;j++)
-
{
-
scanf("%d",&n);
-
for (i=0;i<n;i++)
-
{
-
scanf("%d",&a[i]);
-
}
-
int sum=0,maxsum=-1001,first =0, last = 0, temp = 1;
-
for (i=0;i<n;i++)
-
{
-
sum += a[i];
-
if (sum > maxsum)
-
{
-
maxsum = sum;first = temp;last = i+1;
-
}
-
if (sum < 0)
-
{
-
sum = 0;temp = i+2;
-
}
-
}
-
-
printf("Case %d:
%d %d %d
",j,maxsum,first,last);
-
if (j!=t)
-
{
-
printf("
");
-
}
-
}
-
-
return 0;
-
}
-
随着i不断更新maxsum的值,如果为负数,加上下一个数不论这个数是正负,和值必定比这个数下,所以置前负值为0.若全为负数,则只需保留当前最大的负数即可。
原文地址:https://www.cnblogs.com/mingrigongchang/p/6246311.html