题目描述

给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为负数，则返回 -1 。

注意，取余是在得到最大积之后执行的

样例

输入：grid = [[-1,-2,-3],
             [-2,-3,-3],
             [-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1

输入：grid = [[1,-2,1],
             [1,-2,1],
             [3,-4,1]]
输出：8
解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)

输入：grid = [[1, 3],
             [0,-4]]
输出：0
解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)

输入：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

算法分析

状态表示

分别用a[i][j]和b[i][j]记录 从(0, 0)走到(i, j)路径成绩的最小值和最大值

状态计算

当x = grid[i][j] >= 0时

• a[i][j] = min(a[i - 1][j] * x, a[i][j - 1] * x)
• b[i][j] = max(b[i - 1][j] * x, b[i][j - 1] * x)

当x = grid[i][j] < 0时

• a[i][j] = min(b[i - 1][j] * x, b[i][j - 1] * x)
• b[i][j] = max(a[i - 1][j] * x, a[i][j - 1] * x)

注意：长度和宽度最大值是15，因此一条路径最多有(15 + 15 - 1) = 29个数进行相乘，每个数的绝对值是4，因此最大的数可以是 $4^{29}$ 会爆int，因此用long long存储

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    static long INF = Long.MAX_VALUE;
    static int mod = 1000000000 + 7;
    public int maxProductPath(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        long[][] a = new long[n][m];//乘积的最小值
        long[][] b = new long[n][m];//乘积的最大值
        for(int i = 0;i < n;i ++)
        {
            Arrays.fill(a[i], Long.MAX_VALUE);
            Arrays.fill(b[i], Long.MIN_VALUE);
        }
        a[0][0] = b[0][0] = grid[0][0];
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < m;j ++)
            {
                int x = grid[i][j];
                if(i > 0)
                {
                    if(x > 0) 
                    {
                        a[i][j] = Math.min(a[i][j], a[i - 1][j] * x);
                        b[i][j] = Math.max(b[i][j], b[i - 1][j] * x);
                    }
                    else
                    {
                        a[i][j] = Math.min(a[i][j], b[i - 1][j] * x);
                        b[i][j] = Math.max(b[i][j], a[i - 1][j] * x);
                    }
                }

                if(j > 0)
                {
                    if(x > 0) 
                    {
                        a[i][j] = Math.min(a[i][j], a[i][j - 1] * x);
                        b[i][j] = Math.max(b[i][j], b[i][j - 1] * x);
                    }
                    else
                    {
                        a[i][j] = Math.min(a[i][j], b[i][j - 1] * x);
                        b[i][j] = Math.max(b[i][j], a[i][j - 1] * x);
                    }
                }
            }
        if(b[n - 1][m - 1] < 0) return -1;
        return (int)(b[n - 1][m - 1] % mod);
    }
}