Question

有一道ACM竞赛题，题目我看着貌似简单，就简单写了，当然是错的，只是简单的求和。请高手分析它难在哪？

Description
我很强壮，我爱吃菠菜，我是大力水手波比。
可是最近波比遇到麻烦了，因为他心爱的女朋友奥列夫被海盗抢走了。为了救出他的女朋友，波比准备直捣海盗老巢。
时代在进步，菠菜也出了新品种。现在的增强版菠菜被放在连续的若干个罐子里，每罐菠菜都有固定的力量值。有的可以帮助增加力量，而有的就比较悲剧了，反而会减弱力量。
波比现在没有力量，而他只能从这一连串的菠菜罐子中选吃其中的一段的连续罐子来补充力量。
现在已知菠菜罐子总数n和每罐菠菜的力量值，求出波比可以获得的最大力量。
Input
第一行，一个整数n(1≤ n ≤1000000),表示n个菠菜罐
第二行，n个整数，依次每个菠菜罐的力量值
Output
一行，波比可以获得的最大力量
Sample Input
4
4 -3 2 5Sample Output
8
谢谢大家热心帮助，我写了一个，但是在OJ上提示wrong answer,不知为何？还请在指教……谢谢！
#include<stdio.h>
void main()
{
int i, n,sum,smax;
int value[10000000];
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&value[i]);
}
sum=0;smax=0;
for(i=1;i<=n;i++)
{
if(sum>=0)

sum=sum+value[i];
else sum=0;
if(sum>smax)
{
smax=sum;
}

}
printf("%d",smax);
getch();
}

Answer 1

难点就是要考虑时间复杂度。
如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是，由于长度为n的数组有O(n2)个子数组；而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)。
主要是要理解：当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。
算法思路：时间复杂度是O(n)
假设每罐菠菜的力量值数组为value[n]
1.初始化sum与Maxsum分别等于0.
for(int i=0;i<n;i++)
{
sum+=value[i];
if(sum<0)
sum=0;
if(sum>Maxsum)
Maxsum=sum;
}
if(Maxsum=0)
{
//表示Value数组里面都是负数
求出value数组里面最大的数，然后赋值给Maxsum
}

追问

你好，谢谢提示，根据你的建议，我写了如下程序，我感觉挺对的，可是在OJ上提示的是wrong answer，不知为何，而且，在定义那个value【1000000】时候，win-tc提示数组太小，怎么回事？？谢谢

追答

2个问题
1.value最好动态new,根据实际输入数据个数来决定大小，我写的value[n],是为了简化描述。
2.你忘记了考虑输入的值全负的情况。要加上：
if(Maxsum=0)
{
//表示Value数组里面都是负数
求出value数组里面最大的数，然后赋值给Maxsum
}

Answer 2

关键在于有负力量值，而且是要求最大力量段。不过算法也好解决。

sum计算最大力量值，begin计录最大力量段开始位置，end计录结束位置。
从第一个数开始计算，如果为正数，则累加到sum中，依次直到遇到第一个负数。用之前的sum和负数比，如果负数大，则前begin尝试找下一个力量段，如果正数还大，就减去负数之后继续累加。

其实就一个原则，只要负的力量值还没有大到可以抵消之前积累的正力量值，就把之前的段统计进来，一旦抵消或者变负了，之前的段就可以丢弃了。当然，如果后面的段没有比之前的段大的，之前的段就是最大的段。

Answer 3

#include<stdio.h>
int value[10000001];
void main()
{
int i, n,sum,smax;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&value[i]);
}
sum=0;smax=0;
for(i=1;i<=n;i++)
{
if(sum<0)
sum=0;
sum=sum+value[i];
if(sum>smax)
{
smax=sum;
}
}
printf("%d\n",smax);
}

Answer 4

1.你给出的题的答案，是求所有数的总和。
2.若求最大值。可以把负数忽略掉，求正数的和

Answer 5

最大子段和问题，用动态规划化降低时间复杂度