编程之美2.15 子数组之和的最大值（二维）

问题描述：

我们之前在前面分析了一维数组的子数组最大值的问题，那么如果是二维数组又该如何分析？

一维数组分析：http://www.cnblogs.com/panpannju/p/3732201.html

解法：

1. 暴力解法-------O(N^2*M^2*Sum)

2. 分块计算-------O(N^2*M^2)

3. 变换成一维计算-------O(N^2*M)或者O(M^2*N)

具体思路和代码（本代码是以2*5的矩阵举例）

1. 暴力解法-------O(N^2*M^2*Sum)

思路：固定住子矩阵的四个角，然后依次计算矩阵元素之和，找到最大的。

代码：

 1 int Sum(int A[][5],int i_0,int i_1,int j_0,int j_1)
 2 {
 3     int sum = 0;
 4     for(int i = i_0; i <= i_1; i++)
 5         for(int j = j_0; j<= j_1; j++)
 6             sum += A[i][j];
 7     return sum;
 8 }
 9 
10 int f(int A[][5], int m, int n)
11 {
12     int max = -1000;
13     for(int i_0 = 0; i_0 < m; i_0++)
14         for(int i_1 = i_0; i_1 < m; i_1++)
15             for(int j_0 = 0; j_0 < n; j_0++)
16                 for(int j_1 = j_0; j_1 < n; j_1++)
17                 {
18                     int s = Sum(A,i_0,i_1,j_0,j_1);
19                     if(s > max)
20                         max = s;
21                 }
22     return max;
23 }

2. 分块计算-------O(N^2*M^2)

思路：我们计算从（0,0）顶点到每一个点的子矩阵的和，并存储。

例如：要计算下图红色部分的和=蓝色-绿色-黄色+红色

代码：

 1 int f2(int A[][5], int m, int n)
 2 {
 3     int (*p)[6] = new int[m+1][6];
 4     //为了后面计算的方便，我们对数组进行扩展
 5     //每一行的最前面一个数=0
 6     for(int i = 0; i <= m; i++)
 7         p[i][0] = 0;
 8     //每一列的最上面一个数=0
 9     for(int j = 0; j <= n; j++)
10         p[0][j] = 0;
11     for(int i = 1; i <= m ;i++)
12         for(int j = 1; j<= n; j++)
13         {
14             p[i][j] = Sum(A,0,i-1,0,j-1);
15             cout << p[i][j] <<endl;
16         }
17     int max = p[0][0];
18     for(int i_0 = 1; i_0 <= m; i_0++)
19         for(int i_1 = i_0; i_1 <= m; i_1++)
20             for(int j_0 = 0; j_0 <= n; j_0++)
21                 for(int j_1 = j_0; j_1 <= n; j_1++)
22                 {
23                     int s = p[i_1][j_1] - p[i_0-1][j_1] - p[i_1][j_0-1] + p[i_0-1][j_0-1];
24                     if(s > max)
25                         max = s;
26                 }
27     return max;
28 }

3. 变换成一维计算-------O(N^2*M)或者O(M^2*N)

思路：将二维数组当做一位数组来做，先固定行，再求列。或者先固定列，再求行。

代码：

 1 //一维数组求最大和子数组
 2 int MaxSum3(int A[], int n)
 3 {
 4     int start = A[0];
 5     int max = A[0];
 6     for(int i = 1; i < n; i++)
 7     {
 8         if(start < 0)
 9             start = 0;
10         start += A[i];
11         if(start > max)
12             max = start;
13 
14     }
15     return max;
16 }
17 
18 
19 //将二维数组当做一位数组来做，先固定行，再求列。或者先固定列，再求行。
20 int f3(int A[][5], int m, int n)
21 {
22     int max = -1000;
23     for(int i = 0; i < m; i++)
24         for(int j = i; j < m; j++)
25         {
26             int *a = new int [n];
27             for(int k = 0; k < n; k++)
28             {
29                 a[k] = 0;
30                 for(int t = i; t <= j; t++)
31                     a[k] += A[t][k];
32             }
33             int s = MaxSum3(a,n);
34             if(s > max)
35                 max = s;
36         }
37     return max;
38 }