1594. Maximum Non Negative Product in a Matrix

题目信息

题号:

1594

难度:

Medium

主题:

矩阵、动态规划、最大最小乘积

原题:

LeetCode 1594

重点:

从左上角到右下角只能向右或向下;负数会交换最大与最小乘积状态,最终最大乘积为负时返回 -1

题目重述

给定整数矩阵 grid。从左上角出发,每一步只能向右或向下,直到右下角。路径乘积是经过所有格子元素的乘积。

请返回所有路径中最大的非负乘积对 10^9 + 7 取模后的结果。若每条路径乘积都为负数,返回 -1。

1 <= grid.length, grid[i].length <= 15,-4 <= grid[i][j] <= 4。

自建示例

应在正负两条路径中选择非负最大值:

输入:grid = [[1,-2],[3,4]]
输出:12
解释:向下再向右的乘积为 1*3*4=12,另一条路径乘积为 -8。

单格负数矩阵没有非负路径:

输入:grid = [[-1]]
输出:-1
解释:唯一路径乘积为负数。