一本通-1282：最大子矩阵（二维最长连续子序列和）

【题目描述】 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。

比如，如下4 × 4的矩阵

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

的最大子矩阵是

9 2

-4 1

-1 8

这个子矩阵的大小是15。

【输入】 输入是一个N×N的矩阵。输入的第一行给出N(0<N≤100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。

【输出】 输出最大子矩阵的大小。

【输入样例】 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2

【输出样例】 15

---

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int> > matrix(105, vector<int>(105));
vector<int> d(105), tmp(105);

int largestCotinuousSequenceSum()
{
    fill(d.begin(), d.begin() + n, 0);

    int tmpSum = tmp[0], maxSum = tmp[0];
    for (int i = 1; i < n; ++i) {
        tmpSum = max(tmpSum + tmp[i], tmp[i]);
        maxSum = max(maxSum, tmpSum);
    }

    return maxSum;
}

int largestSubmatrixSum()
{
    int res = INT_MIN;
    for (int i = 0; i < n; ++i) {
        fill(tmp.begin(), tmp.begin() + n, 0);
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                tmp[k] += matrix[j][k];
            }
            res = max(res, largestCotinuousSequenceSum());
        }
    }

    return res;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }

    cout << largestSubmatrixSum() << endl;

    return 0;
}