最大子段和

题目：给定由n个整数（可能为负数）组成的序列a1、a2、.......an。求该序列形如（ai+....+ak）其中i等于i、i+1、......连续的正整数。当所有整数均为负数时，设定其最大正整数和为0.因此对应最优值为：
                                         max{0, max (ai+....+ak)}
1>最简单的解法：
思路：将所有的和情况进行比较，获取最后结果。
时间复杂度：O(n^2)

int max_in_he1(int a[],int l, int r)
{
    int i ,j,k;
    int sum=0,all=0;
    for(i=l;i<r;i++){
         sum =0;
        for(j=i;j<r;j++){
            sum+=a[j];
        if(all<sum)
            all=sum;
        }
    }
    printf("res1 = %d \n",all);
    return all;
}

2>最大子段和问题的动态规划
思路：利用一个新的容量来确定情况选择，一个变量用来存取最大字段和。
思路如果b>0时，则将a[i]加上，否则 b=a[i];
           b = max {b , b+ a[i]}
代码：

int max_in_he2(int a[], int l, int r)
{
int i=0;
int sum =0,all=0;

for(i=l;i
{
if(sum>0)
sum+=a[i];
else
sum=a[i];
if(sum>all)
all=sum;
}
printf("res2 = %d \n",all);
return all;
}