当前位置: 面试刷题>> 最大乘积路径 (经典算法题500道)


题目描述补充

在一个给定的二维网格中,每个格子包含一个整数。路径被定义为从网格的左上角(第一行第一列)开始,每次只能向右或向下移动,直到到达右下角(最后一行最后一列)。我们需要找到一条路径,使得路径上所有数字的乘积最大。由于乘积可能非常大,因此返回的结果需要对10^9 + 7取模。如果网格中存在负数,考虑负数乘负数可能得到正数,从而增加乘积的大小。

示例

网格:
[-2, 3, -4]
[5, 6,  -1]
[2, -7,  8]
[3, 6,  -9]

从左上角到右下角,最大乘积路径为:5 * 6 * -1 * 8 = 240,对10^9 + 7取模后仍为240。

解题思路

  1. 初始化两个二维数组,分别用于存储到达每个位置的最大乘积和最小乘积(因为负数乘以负数可能成为最大乘积)。
  2. 遍历网格,对于每个位置,计算从左上角到达该位置的最大乘积和最小乘积(考虑向右和向下两个方向)。
  3. 注意处理负数和零的情况,因为负数的乘积在路径中可能转变为最大乘积。
  4. 遍历结束后,右下角位置的最大乘积数组中的值即为所求。

PHP代码示例

function maxProductPath($grid) {
    $MOD = pow(10, 9) + 7;
    $m = count($grid);
    $n = count($grid[0]);
    
    $maxProduct = array_fill(0, $m, array_fill(0, $n, 0));
    $minProduct = array_fill(0, $m, array_fill(0, $n, PHP_INT_MAX));
    
    $maxProduct[0][0] = $minProduct[0][0] = $grid[0][0];
    
    // 初始化第一行和第一列
    for ($i = 1; $i < $m; $i++) {
        $maxProduct[$i][0] = $minProduct[$i][0] = $maxProduct[$i-1][0] * $grid[$i][0];
    }
    for ($j = 1; $j < $n; $j++) {
        $maxProduct[0][$j] = $minProduct[0][$j] = $maxProduct[0][$j-1] * $grid[0][$j];
    }
    
    // 填充剩余的格子
    for ($i = 1; $i < $m; $i++) {
        for ($j = 1; $j < $n; $j++) {
            $maxProduct[$i][$j] = max($maxProduct[$i-1][$j], $maxProduct[$i][$j-1]) * $grid[$i][$j];
            $minProduct[$i][$j] = min($minProduct[$i-1][$j], $minProduct[$i][$j-1]) * $grid[$i][$j];
            
            // 更新最大乘积,考虑当前位置为负时的情况
            if ($grid[$i][$j] < 0) {
                $temp = $maxProduct[$i][$j];
                $maxProduct[$i][$j] = min($minProduct[$i-1][$j], $minProduct[$i][$j-1]) * $grid[$i][$j];
                $minProduct[$i][$j] = $temp;
            }
        }
    }
    
    return ($maxProduct[$m-1][$n-1] + $MOD) % $MOD; // 防止负数
}

Python和JavaScript代码示例 可以通过类似的方式实现,主要逻辑相同,但需要注意数据类型和库函数的使用差异。由于篇幅限制,这里不再赘述完整的Python和JavaScript代码,但可以在码小课网站中找到更多相关内容学习。

推荐面试题