题目大意：
矩阵的最大非负积
给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对109 + 7 取余 的结果。如果最大积为负数，则返回-1 。
注意，取余是在得到最大积之后执行的。
示例 1：
输入：grid = [[-1,-2,-3], [-2,-3,-3], [-3,-3,-2]] 输出：-1 解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1
示例 2：
输入：grid = [[1,-2,1], [1,-2,1], [3,-4,1]] 输出：8 解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)
示例 3：
输入：grid = [[1, 3], [0,-4]] 输出：0 解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)
示例 4：
输入：grid = [[ 1, 4,4,0], [-2, 0,0,1], [ 1,-1,1,1]] 输出：2 解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)
提示：
1 <= rows, cols <= 15-4 <= grid[i][j] <= 4
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1594
解题思路分析：
这是一点典型的动态规划题目，对于DP题目我比较喜欢使用递归方式来解题。本题也不例外，实际上使用递归方式解DP题目与dfs深度优先搜索的思路非常类似。以本题为例，由于我们无法一眼看出哪一种路线的乘积最大，因此，我们必须尝试走完每一条路线后才能做出比较。dfs递归方式的核心即是遍历每一条路径。
如果本题中不包含负数，将是一道非常简单的题目，但由于负数的存在，最大非负数乘积并不一定是多个正数的乘积，也有可能是偶数个负数的乘积。因此递归时，我们需要2个记忆数组，来保存当前路径中的最大乘积，与最小乘积（如果最小乘积与当前数字都是负数时，他们的乘积可能会是最大值）。注意这里的最大乘积与最小乘积都有可能是正数或者负数亦或者是0，解题时我们分别将他们与当前数字相乘，再使用得到的结果分别更新当前最大值与最小值。
dfs递归中，对于当前点，在不越界的前提下，我们可以向下走，或者向右走。因此，当前点到达终点的最大乘积将在下面4中可能中产生：
max[r][c]=Math.max(max[r+1][c]*grid[r][c],max[r][c]); // 下一步到达终点的最大乘积与当前数字乘积 max[r][c]=Math.max(min[r+1][c]*grid[r][c],max[r][c]); // 下一步到达终点的最小乘积与当前数字乘积 max[r][c]=Math.max(max[r][c+1]*grid[r][c],max[r][c]); // 右一步到达终点的最大乘积与当前数字乘积 max[r][c]=Math.max(min[r][c+1]*grid[r][c],max[r][c]); // 右一步到达终点的最小乘积与当前数字乘积
同理当前点到终点的最小乘积也将在上述4重结果中产生。其中max[r+1][c]，min[r+1][c]，max[r][c+1]，min[r][c+1]将在递归子函数中取得。递归的结束条件为当前点为终点时（右下角），当前点到终点（也就是自身）的最大乘积与最小成绩都是当前点的数值。
最终我们求解的是起点到终点的最大乘积，如果该乘积为负数，返回-1。
实现代码：
Long[][] max;
Long[][] min;
public int maxProductPath(int[][] grid) {
max=new Long[grid.length][grid[0].length];
min=new Long[grid.length][grid[0].length];
help(grid,0,0);
if(max[0][0]<0) return -1;
return (int)(max[0][0]%1000000007);
}
void help(int[][] grid, int r, int c){
if(r==grid.length-1&&c==grid[0].length-1){ // 当前点为终点
max[r][c]=(long)grid[r][c];
min[r][c]=(long)grid[r][c];
return;
}
if(max[r][c]!=null) return; // 当前点已经递归过
max[r][c]=Long.MIN_VALUE;
min[r][c]=Long.MAX_VALUE;
if(r+1<grid.length){ // 可以向下走
help(grid, r+1, c);
// 更新最大值为下一步到达终点的最大乘积与当前数字乘积
max[r][c]=Math.max(max[r+1][c]*grid[r][c],max[r][c]);
// 更新最大值为下一步到达终点的最小乘积与当前数字乘积
max[r][c]=Math.max(min[r+1][c]*grid[r][c],max[r][c]);
// 更新最小值为下一步到达终点的最大乘积与当前数字乘积
min[r][c]=Math.min(max[r+1][c]*grid[r][c],min[r][c]);
// 更新最小值为下一步到达终点的最小乘积与当前数字乘积
min[r][c]=Math.min(min[r+1][c]*grid[r][c],min[r][c]);
}
if(c+1<grid[0].length){ // 可以向右走
help(grid, r, c+1);
// 更新最大值为右一步到达终点的最大乘积与当前数字乘积
max[r][c]=Math.max(max[r][c+1]*grid[r][c],max[r][c]);
// 更新最大值为右一步到达终点的最小乘积与当前数字乘积
max[r][c]=Math.max(min[r][c+1]*grid[r][c],max[r][c]);
// 更新最小值为右一步到达终点的最大乘积与当前数字乘积
min[r][c]=Math.min(max[r][c+1]*grid[r][c],min[r][c]);
// 更新最小值为右一步到达终点的最小乘积与当前数字乘积
min[r][c]=Math.min(min[r][c+1]*grid[r][c],min[r][c]);
}
}本题解法执行时间为3ms。
Runtime: 3 ms, faster than 50.00% of Java online submissions for Maximum Non Negative Product in a Matrix.
Memory Usage: 41.5 MB, less than 25.00% of Java online submissions for Maximum Non Negative Product in a Matrix.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1594-maximum-non-negative-product-in-a-matrix-解题思路分析/