最大子矩阵

文章目錄

昨天去面试，面试官出了一道最大连续子序列的题目后，很快就做出来，因为前不久还做过笔记的。之后出了一道，最大子矩阵的题目。也就是给出一个矩阵，如：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
求它的子矩阵的最大和。
如
9 2
-4 1
-1 8
是最大子矩阵，和为15.​

想了一会之后，找到了一个转化为最大连续子序列的办法。也就是先对列求和，之后再用最大连续子序列的方法。给出这个办法后，还想考虑优化，只是一直想不出来。回来之后，想起编程之美上有类似的题目，看了之后，没想到已经是最优的了。又想起以前在POJ应该做过类似的题目，于是找到了POJ1050- To The Max. 编写代码如下：

#include <stdio.h>
#include <stdlib.h>
#define N 100
int a[N][N];
int b[N];
int max_sub_array(int *a, int n) {
    int max_sum = a[0];
    int sum = a[0];
    for (int i = 1; i < n; i++) {
        if (sum < 0) {
            sum = 0;
        }
        sum += a[i];
        if (sum > max_sum) {
            max_sum = sum;
        }
    }
    return max_sum;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    int max_sum = -127 * 100 * 100;
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            b[k] = 0;
        }
        for (int j = i; j < n; j++) {
            for (int k = 0; k < n; k++) {
                b[k] += a[j][k];
            }
            int sum = max_sub_array(b, n);
            if (sum > max_sum) {
                max_sum = sum;
            }
        }
    }
    printf("%d\n", max_sum);
    return 0;
}