1594. Maximum Non Negative Product in a Matrix

Link

Solution

the max value can come from maxLeft*cur, maxUp*cur,

Don't forget the max value can also come from minLeft * cur or maxLeft *cur

 public int maxProductPath(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        long[][][] dp = new long[row][col][2];
        dp[0][0][0] = dp[0][0][1] = grid[0][0];
        for(int i = 1; i < row; i++){
            dp[i][0][0] = dp[i][0][1] = dp[i-1][0][0] * grid[i][0];
        }
        
        for(int j = 1; j < col; j++){
            dp[0][j][0] = dp[0][j][1] = dp[0][j-1][0] * grid[0][j];
        }
        
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                int cur = grid[i][j];
                long a = cur * Math.max(dp[i-1][j][0], dp[i][j-1][0]);
                long b = cur * Math.min(dp[i-1][j][1], dp[i][j-1][1]);
                dp[i][j][0] = Math.max(a, b);
                dp[i][j][1] = Math.min(a, b);
            }
        }
        if(dp[row-1][col-1][0] < 0) return -1;
        return (int)(dp[row-1][col-1][0] % (1000000007));
    }