# 1594. Maximum Non Negative Product in a Matrix
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/
## 思路
也是一道dp迷宫题
和[0152. Maximum Product Subarray](https://hackmd.io/qpgZUbERQVOXcw9DSBI1Mw)有点像

和传统的最优路径题一样，令```dp[i][j]```表示从左上角走到```(i,j)```的最优代价（即路径乘积最大）。根据规则，```dp[i][j]```仅由```dp[i-1][j]```和```dp[i][j-1]```转移而来。但是不同于以往的套路：

dp[i][j] = max(dp[i][j-1]*nums[i][j], dp[i-1][j]*nums[i][j])

在这里，如果```nums[i][j]```为负数的话，我们希望已知的反而是走到```(i-1,j)```和```(i,j-1)```的最小乘积路径，这样与```nums[i][j]```相乘之后才能得到的是最大乘积路径。这就提醒我们要维护两个状态变量，```dpMax[i][j]```和```dpMin[i][j]```来分别记录到当前的最大乘积路径和最小乘积路径。

dp1[i][j] = max(max(dpMax[i][j-1]*nums[i][j], dpMax[i-1][j]*nums[i][j]), max(dpMin[i][j-1]*nums[i][j], doMin[i-1][j]*nums[i][j]));
dp2[i][j] = min(min(dpMax[i][j-1]*nums[i][j], dpMax[i-1][j]*nums[i][j]), min(dpMin[i][j-1]*nums[i][j], dpMin[i-1][j]*nums[i][j]));

## Code

class Solution {
    public int maxProductPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        long[][] dpMax = new long[m][n];
        long[][] dpMin = new long[m][n];
        int mod = 1000000007;
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 && j==0){
                    dpMax[0][0] = grid[0][0];
                    dpMin[0][0] = grid[0][0];
                }
                else if(i==0){
                    dpMax[i][j] = Math.max(dpMax[i][j-1]*grid[i][j], dpMin[i][j-1]*grid[i][j]);
                    dpMin[i][j] = Math.min(dpMax[i][j-1]*grid[i][j], dpMin[i][j-1]*grid[i][j]);
                }
                else if(j==0){
                    dpMax[i][j] = Math.max(dpMax[i-1][j]*grid[i][j], dpMin[i-1][j]*grid[i][j]);
                    dpMin[i][j] = Math.min(dpMax[i-1][j]*grid[i][j], dpMin[i-1][j]*grid[i][j]);
                }
                else{
                    dpMax[i][j] = Math.max(Math.max(dpMax[i-1][j]*grid[i][j], dpMin[i-1][j]*grid[i][j]), Math.max(dpMax[i][j-1]*grid[i][j], dpMin[i][j-1]*grid[i][j]));
                    dpMin[i][j] = Math.min(Math.min(dpMax[i-1][j]*grid[i][j], dpMin[i-1][j]*grid[i][j]), Math.min(dpMax[i][j-1]*grid[i][j], dpMin[i][j-1]*grid[i][j]));
                }
            }
        }
    
        return dpMax[m-1][n-1]<0?-1:(int)(dpMax[m-1][n-1]%mod);
    }
}