题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

 

下面将逐步，从效率比较低的算法到效率比较高的算法，最后以时间复杂度O（n）的算法来实现求子数组的和的最大值。

1、 最简单的，时间复杂度O（n*n*n）的算法。

    将所有的(i,j)对儿都遍历一遍（i,j满足条件：0=<i<=j<=n），对于每个(i,j)对儿，计算x[i]到x[j]的和，并令其与到当前为止最大的子数组和maxsofar进行比较，若大于后者，则对maxsofar进行重新复制。伪代码如下：

              maxsofar=0

              for i=[0,n)

                    for j=[i,n)

                          sum=0;

                          for k=[i,j]

                                  sum=sum+x[k]  //sum代表x[i]到x[j]的和

                          maxsofar=max(maxsofar,sum) //max函数用来返回maxsofar和sum两者中的最大值

 

2、时间复杂度为O(n*n)的两个算法

     第一个是利用“x[i]到x[j]的和等于x[i]到x[j-1]的和加上x[j]”这一性质。代码是一种的代码稍作调整，伪代码如下：

             maxsofar=0

             for i=[0,n)

                   sum=0

                   for j=[i,n)

                         sum=sum+x[j]

                         maxsofar=max(maxsofar,sum)

      第二个是利用空间来换取时间的一个算法，它将从第一个元素开始到第j+1（j=[0,n)）元素的和都存起来（存在数组cumarr中），这样每次计算x[i]到x[j]的和时，只需用cumarr[j]-cumarr[i-1]即可得到。伪代码如下：

            cumarr[-1]=0             

            for i=[0,n)

                  cumarr[i]=cumarr[i-1]+x[i]

            for i=[0,n)

                  for j=[i,n)

                        sum=cumarr[j]-cumarr[i-1]

                        maxsofar=max(maxsofar,sum)

 

3、利用这个思想（divide-and-conquer recipe）：把解决一个大问题分解成解决几个子问题，然后把这几个子问题的结果整合起来，进而解决这个大问题。   

   利用递归算法。利用下面思路：x[l]到x[u]的最大子数组是下面三种情况之一（假设m=（l+u）/2）：1、x[l]到x[u]的最大子数组完全出现在x[l]到x[m]之间。2、x[l]到x[u]的最大子数组完全出现在x[m]到x[u]之间。3、x[l]到x[u]之间的最大子数组是x[a]到x[b]，其中a<m<b。伪代码如下：

               int maxsum(l,u)   //返回子数组和最大值的函数maxsum

                    if(l>u)

                         return 0

                    if(l==u)

                         return x[l]

                    m=(l+u)/2

                    lmax=sum=0

                    for(i=m;i>=l;i++)

                          sum=sum+x[i]

                          lmax=max(lmax,sum)

                    rmax=sum=0  

                    for(i=m+1;i<=u;i++)

                          sum=sum+x[i]

                          rmax=max(rmax,sum)

                    return max(lmax+rmax,maxsum(l,m),maxsum(m+1,u));

     时间复杂度：T(n)=2T(n/2)+O(n)   可以推得：T(n)=O(nlogn)

 

4、时间复杂度O(n)，最优的一种算法。

     最简单的操作在数组上的算法是：从总左边（x[0]）开始遍历整个数组，一直到最右边结束（x[n-1]），在这个过程中记录到目前为止最大的子数组和maxsofar。maxsofar初始化成0。假如我们已经找到x[0]到x[n-1]之间的最大子数组和，那么x[0]到x[i]之间的最大子数组和是怎样的呢？要么“还是x[0]到x[i-1]之间的最大子数组和”，要么是“从x[i]开始，往前几个连续的数的最大值”。

     在求从x[i]开始，往前几个连续的数的最大值时，用到如下性质：从x[i]开始往前几个连续的数的最大值maxending_i等于(maxending_i-1)+x[i]和0两者之中的最大值，即

                          maxending_i=max((manending_i-1)+x[i],0)

     下面是这个算法的伪代码：

                      maxsofar=0

                      maxendinghere=0

                      for i=[0,n)

                             maxendinghere=max(maxendinghere+x[i],0)

                             maxsofar=max(maxendinghere,maxsofar)

 

 

下面是算法4的C语言代码，可以参考：

 #include<stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))   //定义计算a，b两者中最大值的宏

int maxsum(int arr[],int num)
{
        int i;
        int maxsofar=0;       //maxsofar记录到目前为止的最大值
        int maxendinghere=0;//maxendinghere记录从当前位置开始往前几个连续的数的和的最大值（或0）
        for(i=0;i<num;i++)
        {
                maxendinghere=max(maxendinghere+arr[i],0);
                maxsofar=max(maxsofar,maxendinghere);
        }
        return maxsofar;
}
int main()
{
        int a[8]={1,-2,3,10,-4,7,2,-5};
        int max=maxsum(a,8);
        printf("%d\n",max);
        return 0;
}