二维矩阵中的最大和矩形

2025年3月17日 | 阅读 7 分钟

问题描述： 给定一个二维整数矩阵，我们的目标是找到具有最大可能和的矩形子矩阵。

这是一个经典的动态规划问题，可以使用以下三种方法中的任意一种来解决。

但考虑到各自的时间和空间复杂度，本文讨论了三种方法。

方法一：使用递归

public class MaxSumRectangle {

    // Function to find the maximum sum rectangle within a matrix
    public static int findMaxSumRectangle(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSum = Integer.MIN_VALUE; // Initialize the maximum sum with a very small value

        // Loop through all possible starting and ending points for the submatrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                for (int k = i; k < rows; k++) {
                    for (int l = j; l < cols; l++) {
                        // Calculate the sum of the current submatrix
                        int sum = calculateSubMatrixSum(matrix, i, j, k, l);
                        // Update the maximum sum if the current sum is greater
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }

        return maxSum; // Return the maximum sum found
    }

    // Function to calculate the sum of elements within a submatrix
    public static int calculateSubMatrixSum(int[][] matrix, int startRow, int startCol, int endRow, int endCol) {
        int sum = 0;
        // Iterate through the submatrix and add each element to the sum
        for (int i = startRow; i <= endRow; i++) {
            for (int j = startCol; j <= endCol; j++) {
                sum += matrix[i][j];
            }
        }
        return sum; // Return the calculated sum of the submatrix
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, -1, -4, -20},
            {-8, -3, 4, 2, 1},
            {3, 8, 10, 1, 3},
            {-4, -1, 1, 7, -6}
        };

        // Find the maximum sum rectangle within the given matrix
        int result = findMaxSumRectangle(matrix);
        System.out.println("Maximum Sum Rectangle: " + result);
    }
}

输出

说明

findMaxSumRectangle 函数

该函数负责在输入矩阵中找到最大和子矩阵。它使用四个嵌套循环来遍历矩阵内所有可能的子矩阵。每个子矩阵使用 calculateSubMatrixSum 函数计算其元素之和，如果计算出的和大于当前最大和，则更新最大和。

calculateSubMatrixSum 函数

该函数计算由起始和结束行、列指定的给定子矩阵内元素的和。它使用两个嵌套循环遍历子矩阵，并累加元素之和。

在这种递归方法中，我们遍历所有可能的矩形维度（起始行和列，结束行和列），并使用 calculateSubMatrixSum 方法计算其和。

时间复杂度：O(n^4)

其中“n”是输入矩阵的行数或列数。

对于较大的测试用例，此方法可能会失败。

下面将使用一种称为动态规划的概念来讨论更高效的方法。

由于递归是动态规划的首要步骤，我们可以开始思考需要遵循的后续步骤。

由于存在重叠子问题，我们可以利用记忆化的概念。

方法二：使用记忆化

public class MaxSumRectangle {

    // Function to find the maximum sum rectangle within a matrix
    public static int findMaxSumRectangle(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSum = Integer.MIN_VALUE; // Initialize the maximum sum with a very small value
        int[][] memo = new int[rows][cols]; // Create a memoization matrix

        // Nested loops to iterate through all possible submatrices
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                for (int k = i; k < rows; k++) {
                    for (int l = j; l < cols; l++) {
                        // Calculate the sum of the current submatrix using memoization
                        int sum = calculateSubMatrixSum(matrix, i, j, k, l, memo);
                        // Update the maximum sum if the current sum is greater
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }

        return maxSum; // Return the maximum sum found
    }

    // Function to calculate the sum of elements within a submatrix using memoization
    public static int calculateSubMatrixSum(int[][] matrix, int startRow, int startCol, int endRow, int endCol, int[][] memo) {
        // Check for different cases and use memoized values for efficient calculations
        if (startRow == 0 && startCol == 0) {
            return memo[endRow][endCol];
        } else if (startRow == 0) {
            return memo[endRow][endCol] - memo[endRow][startCol - 1];
        } else if (startCol == 0) {
            return memo[endRow][endCol] - memo[startRow - 1][endCol];
        } else {
            return memo[endRow][endCol] - memo[endRow][startCol - 1] - memo[startRow - 1][endCol] + memo[startRow - 1][startCol - 1];
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, -1, -4, -20},
            {-8, -3, 4, 2, 1},
            {3, 8, 10, 1, 3},
            {-4, -1, 1, 7, -6}
        };

        int[][] memo = new int[matrix.length][matrix[0].length]; // Create a memoization matrix

        // Fill the memoization matrix with cumulative sums of submatrices
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0 && j == 0) {
                    memo[i][j] = matrix[i][j];
                } else if (i == 0) {
                    memo[i][j] = memo[i][j - 1] + matrix[i][j];
                } else if (j == 0) {
                    memo[i][j] = memo[i - 1][j] + matrix[i][j];
                } else {
                    memo[i][j] = memo[i - 1][j] + memo[i][j - 1] - memo[i - 1][j - 1] + matrix[i][j];
                }
            }
        }

        int result = findMaxSumRectangle(matrix); // Find the maximum sum rectangle within the given matrix
        System.out.println("Maximum Sum Rectangle: " + result);
    }
}

输出

时间复杂度：O(rows^2 * cols^2)

说明

findMaxSumRectangle 函数

calculateSubMatrixSum 函数

该函数计算由起始和结束行、列指定的给定子矩阵内元素的和。它使用记忆化技术，利用存储在 memo 矩阵中预先计算的累积和值，来高效地计算子矩阵的和。

由于记忆化的概念会使用额外的堆栈空间。

为了消除这一点，下面讨论了一种更高效的方法，该方法利用了动态规划中称为制表法（Tabulation）的概念。

方法三：制表法（Tabulation）

public class MaxSumRectangle {

    // Function to find the maximum sum rectangle within a matrix
    public static int findMaxSumRectangle(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSum = Integer.MIN_VALUE; // Initialize the maximum sum with a very small value
        int[][] memo = new int[rows + 1][cols + 1]; // Create a memoization matrix with additional row and column

        // Precompute cumulative sum matrix using dynamic programming
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1] - memo[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }

        // Calculate maximum sum rectangle using tabulation
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                for (int k = i; k <= rows; k++) {
                    for (int l = j; l <= cols; l++) {
                        // Calculate the sum of the current submatrix using cumulative sum matrix
                        int sum = memo[k][l] - memo[i - 1][l] - memo[k][j - 1] + memo[i - 1][j - 1];
                        // Update the maximum sum if the current sum is greater
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }

        return maxSum; // Return the maximum sum found
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, -1, -4, -20},
            {-8, -3, 4, 2, 1},
            {3, 8, 10, 1, 3},
            {-4, -1, 1, 7, -6}
        };

        // Find the maximum sum rectangle within the given matrix
        int result = findMaxSumRectangle(matrix);
        System.out.println("Maximum Sum Rectangle: " + result);
    }
}

输出

时间复杂度：O(rows^2 * cols^2)

说明

findMaxSumRectangle 函数

该函数负责在输入矩阵中找到最大和子矩阵。它利用了两个关键步骤：

预计算累积和矩阵 (memo)

它初始化一个带有一个额外行和一个额外列的记忆化矩阵 (memo)，用于存储子矩阵的累积和值。该矩阵通过迭代填充，每个单元格 (memo[i][j]) 存储由左上角 ([0][0]) 和右下角 ([i][j]) 形成的矩形之和。

遍历子矩阵

它使用四个嵌套循环来遍历所有可能的子矩阵起始和结束行、列对。对于每一对，它使用存储在 memo 矩阵中的累积和值来计算相应子矩阵中元素的和。

这是该代码的最优化版本。

下一个主题按排序顺序打印出行列有序矩阵中的所有元素

二维矩阵中的最大和矩形

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二维矩阵中的最大和矩形

相关帖子

归并排序和快速排序的区别

与给定数字最接近的三元组和

检查表达式中的括号是否平衡 (格式正确性)

C 语言中移除 BST 范围外的键

如何在 C++ 中使用 Qdebug 打印字符串字面量和 Qstring

大 O、大 Theta 和大 Omega 表示法之间的区别

数组中每个元素左边大于或等于它的最近元素

哈希及其应用

C++ 中按第一个和第二个元素排序的对优先队列

生成所有子数组

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器