1594. Maximum Non Negative Product in a Matrix¶
题目信息¶
- 题号:
1594
- 难度:
Medium
- 主题:
矩阵、动态规划、最大最小乘积
- 原题:
- 重点:
从左上角到右下角只能向右或向下;负数会交换最大与最小乘积状态,最终最大乘积为负时返回
-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
解释:唯一路径乘积为负数。