Cracking the coding interview--Q20.12

March 8, 2013
作者:Hawstein
出处:http://hawstein.com/posts/20.12.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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),我们可以通过以下式子计算得出:

sum(D) = p[y2][x2] - p[y2][x1-1] - p[y1-1][x2] + p[y1-1][x1-1]

只需要O(1)的时间。

部分和p[i][j]要怎么计算呢?我们可以通过更小的部分和来计算得到它:

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)。 既然如此,我们可以把二维数组一个方向的数累加起来,将它变为一维数组, 然后就转化成了求一维数组子数组之和的最大值。看示意图:

			第k列	第l列
第i行:...	...		...		...
	  ...	...		...		...
第j行:...	...		...		...

在同一列中,我们把第i行到第j行的数加起来,得到如下:

				第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)的时间:

sum(i,j,k) = p[j][k] - p[j][k-1] - p[i-1][k] + p[i-1][k-1]

代码如下:

#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