当前位置: 面试刷题>> 最大矩阵 (经典算法题500道)


题目描述补充

题目:最大矩阵

给定一个二维数组(矩阵)matrix,其中矩阵的每个元素代表一个整数。你需要找到这个矩阵中所有子矩阵(由矩阵中的连续行和列组成的矩形区域)中的最大值,并返回这些最大值中的最大值。

示例输入

matrix = [
  [3, 2, 1],
  [1, 5, 6],
  [4, 0, 8]
]

示例输出

8

解释:在这个矩阵中,最大的子矩阵是 [4, 0, 8],它的最大值是8。

PHP代码示例

function maxMatrix($matrix) {
    if (empty($matrix) || empty($matrix[0])) return 0;

    $rows = count($matrix);
    $cols = count($matrix[0]);
    $max = PHP_INT_MIN;

    for ($r1 = 0; $r1 < $rows; $r1++) {
        $minRow = $matrix[$r1];
        for ($r2 = $r1; $r2 < $rows; $r2++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($r2 == $r1) {
                    $minRow[$c] = $matrix[$r2][$c];
                } else {
                    $minRow[$c] = min($minRow[$c], $matrix[$r2][$c]);
                }
            }

            $currMax = PHP_INT_MIN;
            $sum = 0;
            for ($c = 0; $c < $cols; $c++) {
                $sum += $minRow[$c];
                $currMax = max($currMax, $sum);
                if ($sum < 0) $sum = 0;
            }

            $max = max($max, $currMax);
        }
    }

    return $max;
}

// 示例用法
$matrix = [
    [3, 2, 1],
    [1, 5, 6],
    [4, 0, 8]
];
echo maxMatrix($matrix); // 输出 8

Python代码示例

def maxMatrix(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    max_val = float('-inf')

    for r1 in range(rows):
        min_row = [matrix[r1][c] for c in range(cols)]
        for r2 in range(r1, rows):
            for c in range(cols):
                if r2 > r1:
                    min_row[c] = min(min_row[c], matrix[r2][c])

            curr_max = float('-inf')
            sum_val = 0
            for c in range(cols):
                sum_val += min_row[c]
                curr_max = max(curr_max, sum_val)
                if sum_val < 0:
                    sum_val = 0

            max_val = max(max_val, curr_max)

    return max_val

# 示例用法
matrix = [
    [3, 2, 1],
    [1, 5, 6],
    [4, 0, 8]
]
print(maxMatrix(matrix))  # 输出 8

JavaScript代码示例

function maxMatrix(matrix) {
    if (!matrix.length || !matrix[0].length) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    let max = Number.MIN_SAFE_INTEGER;

    for (let r1 = 0; r1 < rows; r1++) {
        const minRow = [...matrix[r1]];
        for (let r2 = r1; r2 < rows; r2++) {
            for (let c = 0; c < cols; c++) {
                if (r2 > r1) {
                    minRow[c] = Math.min(minRow[c], matrix[r2][c]);
                }
            }

            let currMax = Number.MIN_SAFE_INTEGER;
            let sum = 0;
            for (let c = 0; c < cols; c++) {
                sum += minRow[c];
                currMax = Math.max(currMax, sum);
                if (sum < 0) sum = 0;
            }

            max = Math.max(max, currMax);
        }
    }

    return max;
}

// 示例用法
const matrix = [
    [3, 2, 1],
    [1, 5, 6],
    [4, 0, 8]
];
console.log(maxMatrix(matrix)); // 输出 8

码小课网站分享: 码小课网站中有更多关于算法和数据结构的精彩内容,包括动态规划、贪心算法、图论、搜索与排序等多种主题的详细讲解和实战案例,欢迎大家前来学习交流,不断提升自己的编程技能。

推荐面试题