编程之美2.14 求数组的子数组之和的最大值

问题描述：

一个有N个整数元素的一维数组（A[0], A[1], A[2],...,A[n-1]），这个数组当然有很多子数组，那么子数组之和的最大值是什么呢？

解法：

1. 暴力解法-------O(N^3)

2. 改进版暴力解法-------O(N^2)

*3. 分治算法-------O(NlogN)（暂时未去实现）

4. 数组间关系法-------O(N)

具体思路和代码：

1.暴力解法

思路：Sum[i,...,j]为数组第i个元素到第j个元素的和，遍历所有可能的Sum[i,...,j]。

代码：

 1 int MaxSum1(int A[], int n)
 2 {
 3     int max = A[0];
 4     int sum = 0;
 5     for(int i = 0; i < n; i++)
 6         for(int  j = i; j < n; j++)
 7         {
 8             sum = 0;
 9             for(int k = i; k <= j; k++)
10             {
11                 sum += A[k];
12             }
13             if(sum > max)
14                 max = sum;
15         }
16     return max;
17 }

2. 改进版暴力解法

思路：从上面的代码我们可以发现sum[i,...,j] = sum[i,...,j-1] + A[j]

因此，最后一个循环可以省去。

代码：

 1 int MaxSum2(int A[], int n)
 2 {
 3     int max = A[0];
 4     int sum = 0;
 5     for(int i = 0; i < n; i++)
 6     {
 7         sum = 0;
 8         for(int  j = i; j < n; j++)
 9         {
10             sum += A[j];
11             if(sum > max)
12                 max = sum;
13         }
14     }
15     return max;
16 }

*3. 分治算法（待更新）

4. 数组间关系法

思路：从分治算法中得到提示：可以考虑数组的第一个元素A[0],以及最大的一段数组（A[i],...,A[j]）跟A[0]之间的关系，有以下几种：

（1）：当i=j=0时，元素A[0]本身构成和最大的一段；

（2）：当0=i<j时，和最大一段从A[0]开始；

（3）：当0<i时，元素A[0]和最大的一段没有关系。

代码：

 1 int MaxSum3(int A[], int n)
 2 {
 3     int start = A[0];
 4     int max = A[0];
 5     for(int i = 1; i < n; i++)
 6     {
 7         if(start < 0)
 8             start = 0;
 9         start += A[i];
10         if(start > max)
11             max = start;
12 
13     }
14     return max;
15 }