首页 > 代码库 > 编程之美2.14 求数组的子数组之和的最大值

编程之美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 }