题目
原文：
Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.
译文：
给一个NxN的矩阵，矩阵上每个格子中填有一个整数(正，负或0)， 写代码计算子矩阵之和的最大值。
解答
暴力法，时间复杂度O(n^6 )
最简单粗暴的方法就是枚举所有的子矩阵，求和，然后找出最大值。 枚举子矩阵一共有C(n, 2)*C(n, 2)个(水平方向选两条边，垂直方向选两条边)， 时间复杂度O(n^4 )，求子矩阵中元素的和需要O(n^2 )的时间。 因此总的时间复杂度为O(n^6 )。
部分和预处理，时间复杂度降到O(n^4 )
上面的方法需要O(n^2 )去计算子矩阵中元素的和。 这一部分我们可以在预处理的时候求出部分和，在使用的时候就只需要O(1) 的时间来得到子矩阵中元素的和。
我们用一个二维数组p来保存矩阵的部分和，p[i][j]表示左上角是(1, 1)，(下标从1开始)， 右下角是(i, j)的矩阵中元素的和。这样一来，如果我们要求矩阵(x1, x2, y1, y2) 中元素的和(即上图矩阵D)，我们可以通过以下式子计算得出：
1
sum(D) = p[y2][x2] - p[y2][x1-1] - p[y1-1][x2] + p[y1-1][x1-1]
只需要O(1)的时间。
部分和p[i][j]要怎么计算呢？我们可以通过更小的部分和来计算得到它：
1
p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + A[i][j]
其中A[i][j]是格子(i, j)中的整数。我们只需要O(n^2 ) 的时间即可预处理得到所有的部分和。
降维，O(n^3 )的解法
如果有一个一维的数组，我们要求它子数组之和的最大值，最好的时间复杂度是O(n)。 既然如此，我们可以把二维数组一个方向的数累加起来，将它变为一维数组， 然后就转化成了求一维数组子数组之和的最大值。看示意图：
1
2
3
4
第k列 第l列
第i行：... ... ... ...
... ... ... ...
第j行：... ... ... ...
在同一列中，我们把第i行到第j行的数加起来，得到如下：
1
2
第k列 第l列
只剩下一行：... ... ... ...
这时候我们可以用O(n)的时候算出子数组之和的最大值，假设是第k个元素到第l 个元素的子数组。那么它实际上就对应二维数组中第i，j行，第k，l 列组成的子矩阵的元素和。
枚举i，j行需要O(n^2 )的时间，求一维情况的子数组最大和需要O(n)的时间， 所以总的时间复杂度为O(n^3 )。其中求第k列元素中， 第i行到第j行的元素和可以用部分和求解，仅需要O(1)的时间：
1
sum(i,j,k) = p[j][k] - p[j][k-1] - p[i-1][k] + p[i-1][k-1]
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 100;
int p[MAX_N][MAX_N], A[MAX_N][MAX_N];
void PreCompute(int n){
for(int i=0; i<=n; ++i)
p[0][i] = p[i][0] = 0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + A[i][j];
}
int MaxSum(int n){
int max_sum = 1<<31; //min int
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j){
int cur_sum = 0;
for(int k=1; k<=n; ++k){
int val = p[j][k]-p[j][k-1]-p[i-1][k]+p[i-1][k-1];
if(cur_sum <= 0)
cur_sum = val;
else
cur_sum += val;
if(cur_sum > max_sum)
max_sum = cur_sum;
}
}
return max_sum;
}
int main(){
freopen("20.12.in", "r", stdin);
int n;
cin>>n;
for(int i=1; i<=n; ++i)//元素存储从1开始
for(int j=1; j<=n; ++j)
cin>>A[i][j];
PreCompute(n);
cout<<MaxSum(n)<<endl;
fclose(stdin);
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/03/08/20.12/
