矩阵动态规划-最大子矩阵和

 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

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-28 20:42:50
 * 最后修改: 2024-12-28 20:43:59
 * 文件描述: 暴力求子矩阵和的最大值
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int maxSumRectangle(vector<vector<int>> &mat) {
  
    int n = mat.size();
    int m = mat[0].size();
    int maxSum = INT_MIN;

    for (int up = 0; up < n; up++) {
        for (int left = 0; left < m; left++) {
            for (int down = up; down < n; down++) {
                for (int right = left; right < m; right++) {
                    // Find the sum of submatrix(up, right, down, left)

                    int sum = 0;

                    for (int i = up; i <= down; i++) {
                        for (int j = left; j <= right; j++) {
                            sum += mat[i][j];
                        }
                    }

                    // Update maxSum if sum > maxSum.
                    if (sum > maxSum) {
                        maxSum = sum;
                    }
                }
            }
        }
    }

    return maxSum;
}
int main() {
    vector<vector<int>> mat = {{1, 2, -1, -4, -20}, 
                               {-8, -3, 4, 2, 1}, 
                               {3, 8, 10, 1, 3}, 
                               {-4, -1, 1, 7, -6}};
    int res = maxSumRectangle(mat);
    cout << res << endl;
    return 0;
}

 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

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-28 05:18:47
 * 最后修改: 2024-12-28 21:22:16
 * 文件描述: n∗m矩阵的最大子矩阵和
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;                // 矩阵的行数和列数
    int maxSum = INT_MIN;    // 初始化最大子矩阵和为最小值
    cin >> n >> m;           // 输入矩阵的大小

    // 初始化矩阵和前缀和数组
    vector<vector<int>> matrix(n, vector<int>(m, 0)); 
    vector<vector<int>> prefixSum(n, vector<int>(m, 0)); 

    // 输入矩阵的元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }

    // 构建前缀和数组，计算每列的累积和
    for (int i = 0; i < m; i++) { 
        prefixSum[0][i] = matrix[0][i]; // 第一行的前缀和等于矩阵第一行的值
    }
    for (int i = 1; i < n; i++) { 
        for (int k = 0; k < m; k++) {
            prefixSum[i][k] = prefixSum[i - 1][k] + matrix[i][k]; // 累加上一行的值
        }
    }

    // 枚举子矩阵的上下边界 i 和 j
    for (int i = 0; i < n; i++) {          // 枚举子矩阵的上边界
        for (int j = i; j < n; j++) {      // 枚举子矩阵的下边界
            int currentSum = 0;           // 当前列范围的最大和
            int columnSum = INT_MIN;      // 当前列的累加和（初始化为最小值）

            for (int k = 0; k < m; k++) { // 遍历所有列
                if (i == 0) {
                    columnSum = prefixSum[j][k]; // 如果上边界是第0行，直接使用前缀和
                } else {
                    columnSum = prefixSum[j][k] - prefixSum[i - 1][k]; // 计算从第i行到第j行的累加和
                }

                // 使用 Kadane 算法计算一维最大子数组和
                currentSum = max(columnSum, columnSum + currentSum); // 更新当前最大列和
                maxSum = max(maxSum, currentSum);                    // 更新全局最大子矩阵和
            }
        }
    }

    // 输出结果：最大子矩阵和
    cout << maxSum << endl;
    return 0;
}