最大子矩阵和

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<int> maxContinuousSubsectionSum(vector<int> nums) {
    long n = nums.size();
    if (n <= 0)
        return {0, 0, 0};
    vector<int> dp(n);
    vector<int> start(n);
    dp[0] = nums[0];
    start[0] = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i];
            start[i] = start[i - 1];
        } else {
            dp[i] = nums[i];
            start[i] = i;
        }
    }
    int left = 0, right = 0;
    int maximum = dp[0];
    for (int i = 1; i < n; i++) {
        if (dp[i] > maximum) {
            maximum = dp[i];
            left = start[i];
            right = i;
        }
    }
    return {maximum, left, right};
}

vector<int> maxSubMatrixSum(vector<vector<int>> mat) {
//    m 行，n 列
    long m = mat.size();
    if (m <= 0)
        return {0, 0, 0, 0, 0};
    long n = mat[0].size();
    if (n <= 0)
        return {0, 0, 0, 0, 0};

    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            mat[i][j] += mat[i - 1][j];
        }
    }

    int maximum = mat[0][0];
    int top = 0, bottom = 0, left = 0, right = 0;
    for (int i = 0; i < m; i++) {
        for (int j = i; j < m; j++) {
            vector<int> tmp(n);
            for (int k = 0; k < n; k++) {
                if (i == 0) {
                    tmp[k] = mat[j][k];
                } else {
                    tmp[k] = mat[j][k] - mat[i - 1][k];
                }
            }
            vector<int> currentMax = maxContinuousSubsectionSum(tmp);
            if (currentMax[0] > maximum) {
                maximum = currentMax[0];
                left = currentMax[1];
                right = currentMax[2];
                top = i;
                bottom = j;
            }
        }
    }
    return {maximum, top, bottom, left, right};
}

int main() {
    vector<vector<int>> nums = {{0,  -2, 7,  0},
                                {9,  2,  -6, 2},
                                {-4, 1,  -4, 1},
                                {-1, 8,  0,  -2},
                                {-1, 2,  0,  -2}};

    vector<int> res = maxSubMatrixSum(nums);
    int maximum = res[0], top = res[1], bottom = res[2], left = res[3], right = res[4];

    cout << "最大子矩阵和为：" << maximum << endl;
    cout << "左上角和右下角坐标为：";
    cout << "(" << top << ", " << left << "), (" << bottom << ", " << right << ")" << endl;
    return 0;
}

参考：https://blog.csdn.net/beiyeqingteng/article/details/7056687