LeetCode 1594. 矩阵的最大非负积

Categories:

题目描述
思路分析
1. 解法一：最大最小 DP（推荐）
相似题目

题目描述

✅ 1594. 矩阵的最大非负积

思路分析

解法一：最大最小 DP（推荐）

核心思路：

负数会翻转乘积大小，需要同时维护最大与最小乘积。

maxDp[i][j]、minDp[i][j] 表示到达 (i,j) 的最大/最小乘积。

由上方与左方转移，取四种组合中的最大与最小。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示矩阵尺寸。

空间复杂度：O(m * n)，用于 DP 表。

class Solution {
    public int maxProductPath(int[][] grid) {
        int mod = 1_000_000_007;
        int m = grid.length;
        int n = grid[0].length;

        long[][] maxDp = new long[m][n];
        long[][] minDp = new long[m][n];
        maxDp[0][0] = grid[0][0];
        minDp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++) {
            maxDp[i][0] = maxDp[i - 1][0] * grid[i][0];
            minDp[i][0] = maxDp[i][0];
        }
        for (int j = 1; j < n; j++) {
            maxDp[0][j] = maxDp[0][j - 1] * grid[0][j];
            minDp[0][j] = maxDp[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                long a = maxDp[i - 1][j] * grid[i][j];
                long b = minDp[i - 1][j] * grid[i][j];
                long c = maxDp[i][j - 1] * grid[i][j];
                long d = minDp[i][j - 1] * grid[i][j];

                long maxVal = Math.max(Math.max(a, b), Math.max(c, d));
                long minVal = Math.min(Math.min(a, b), Math.min(c, d));

                maxDp[i][j] = maxVal;
                minDp[i][j] = minVal;
            }
        }

        long ans = maxDp[m - 1][n - 1];
        if (ans < 0) {
            return -1;
        }

        return (int) (ans % mod);
    }
}

func maxProductPath(grid [][]int) int {
	const mod = 1000000007
	m, n := len(grid), len(grid[0])

	maxDp := make([][]int64, m)
	minDp := make([][]int64, m)
	for i := 0; i < m; i++ {
		maxDp[i] = make([]int64, n)
		minDp[i] = make([]int64, n)
	}
	maxDp[0][0] = int64(grid[0][0])
	minDp[0][0] = int64(grid[0][0])

	for i := 1; i < m; i++ {
		maxDp[i][0] = maxDp[i-1][0] * int64(grid[i][0])
		minDp[i][0] = maxDp[i][0]
	}
	for j := 1; j < n; j++ {
		maxDp[0][j] = maxDp[0][j-1] * int64(grid[0][j])
		minDp[0][j] = maxDp[0][j]
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			val := int64(grid[i][j])
			a := maxDp[i-1][j] * val
			b := minDp[i-1][j] * val
			c := maxDp[i][j-1] * val
			d := minDp[i][j-1] * val

			maxVal := max64(max64(a, b), max64(c, d))
			minVal := min64(min64(a, b), min64(c, d))

			maxDp[i][j] = maxVal
			minDp[i][j] = minVal
		}
	}

	ans := maxDp[m-1][n-1]
	if ans < 0 {
		return -1
	}

	return int(ans % mod)
}

func max64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

相似题目

题目	难度	考察点
64. 最小路径和	中等	动态规划
152. 乘积最大子数组	中等	最大最小 DP
174. 地下城游戏	困难	动态规划
120. 三角形最小路径和	中等	动态规划
221. 最大正方形	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/61944218