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

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

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

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

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

#include
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);
}

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

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