最大子阵和

发表于 | 分类于

1. 思路

最大子矩阵和是最大字段和的一个拓展延申。相当于把原本一维的数组延展到二维上面来。

首先来列一下最大子段和的算法: 

1
2
3
4
5
6
7
8
9
10
int maxSubArray(int arr[], size_t n)
{
    int maxSum = arr[0], dp = 0;
    for (int i = 0; i < n; ++i)
    {
        dp = max(arr[i], dp + arr[i]);
        maxSum = max(maxSum, dp);
    }
    return maxSum;
}

那么如何解决最大子矩阵和的问题呢？核心的思想是把二维矩阵变为一维数组，然后求解一个最大子段和问题。

什么意思？假如有这么一个矩阵:

\[ \begin{pmatrix} 0 & -2 & -7 & 0\\ 9 & 2 & -6 & 2\\ -4 & 1 & -4 & 1\\ -1 & 8 & 0 & 2 \end{pmatrix} \]

如果我们能把它变成这样:

\[ \begin{pmatrix} 0 & -2 & -7 & 0\\ 9 & 2 & -6 & 2\\ -4 & 1 & -4 & 1\\ -1 & 8 & 0 & 2 \end{pmatrix} \Rightarrow \begin{pmatrix} a_0 & 0 & -2 & -7 & 0\\ a_0+a_1 & 9 & 0 & -15 & 2\\ a_0+a_1+a_2 & 5 & 1 & -19 & 1\\ a_0+a_1+a_2+a_3 & 4 & 9 & -19& 3\\ a_1 & 9 & 2 & -6 & 2\\ a_1+a_2 & 5 & 3 & -10& 3\\ a_1+a_2+a_3 & 4 & 11 & -10 & 5\\ a_2&-4 & 1 & -4& 1\\ a_2+a_3&-5 & 9 &-4 & 3\\ a_3&-1 & 8 & 0 & 2 \end{pmatrix} \]

然后对于新的矩阵的的每一行都求一次最大字段和，取其最大值，就是最大子阵和了。

也就是这样:

1
2
3
4
5
6
7
MaxSubMatrix(matrix):
    maxVal = 负无穷
    for i = 1:n:
        for j = i:n:
            array = sum(matrix[i:j, :], 沿着纵轴)
            maxVal = max(maxVal, array的最大子段和)
    return maxVal

以上的伪代码就是算法的基本思想，其中 matrix[i:j, :] 的意思是 matrix 从 i 到 j 的一个闭区间子矩阵。

不过上面的算法还有一些可以改进的地方。

2. 改进

什么地方可以改进呢？在于 sum(matrix[i:j, :], 沿着纵轴)，这实在是太花时间了！想想看把，本来已经有一个二重循环了，最里面还要对一个子矩阵做遍历，这加起来足足有 \(O(n^4)\) 的复杂度了。

所以为了简化这一操作，我们可以做一个预处理，我们可以使用一个辅助矩阵 AxisSum，其中

\[ \large AxisSum[i][j] = \large \sum_{k = 0}^{i}{Matrix[k][j]} \]

这样一来我们可以轻松的计算矩阵中任意一列的子段之和了，比如现在我们想要将矩阵第a行到第b行之间的子矩阵进行压缩考察，那么有:

\[ Array[j] = \begin{cases} AxisSum[b][j] - AxisSum[a - 1][j] & (a > 1)\\ Axis[1][j] & (a = 1) \end{cases} \]

3. 完整代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using namespace std;

int n;
/*mat[i][j]表示从第一行到第i+1行的j列的和*/
long mat[100][100];
long arr[100];

void Input()
{
    for (int j = 0; j < n; ++j)
        cin >> mat[0][j];
    for (int i = 1; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> mat[i][j];
            mat[i][j] += mat[i - 1][j];
        }
    }
}


int maxSubArray()
{
    int maxSum = arr[0], dp = 0;
    for (int i = 0; i < n; ++i)
    {
        dp = max(arr[i], dp + arr[i]);
        maxSum = max(maxSum, dp);
    }
    return maxSum;
}

void DP()
{
    int maxVal = mat[0][0];
    for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            for (int k = 0; k < n; ++k)
            {
                int high = mat[j][k];
                int low = 0;
                if (i > 0)
                    low = mat[i - 1][k];
                arr[k] = high - low;
            }
            int val = maxSubArray();
            maxVal = max(val, maxVal);
        }
    }
    cout << maxVal << endl;
}

int main()
{
    while (cin >> n)
    {
        Input();
        DP();
    }
    return 0;
}