LeetCode [1594] Maximum Non Negative Product in a Matrix

 1594. Maximum Non Negative Product in a Matrix

Medium

You are given a rows x cols matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.

Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (rows - 1, cols - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.

Return the maximum non-negative product modulo 109 + 7. If the maximum product is negative return -1.

Notice that the modulo is performed after getting the maximum product.

 

Example 1:

Input: grid = [[-1,-2,-3],
               [-2,-3,-3],
               [-3,-3,-2]]
Output: -1
Explanation: It's not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.

Example 2:

Input: grid = [[1,-2,1],
               [1,-2,1],
               [3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is in bold (1 * 1 * -2 * -4 * 1 = 8).

Example 3:

Input: grid = [[1, 3],
               [0,-4]]
Output: 0
Explanation: Maximum non-negative product is in bold (1 * 0 * -4 = 0).

Example 4:

Input: grid = [[ 1, 4,4,0],
               [-2, 0,0,1],
               [ 1,-1,1,1]]
Output: 2
Explanation: Maximum non-negative product is in bold (1 * -2 * 1 * -1 * 1 * 1 = 2).

 

Constraints:

• 1 <= rows, cols <= 15
• -4 <= grid[i][j] <= 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

class Solution { int M = 1000000007; public int maxProductPath(int[][] grid) { int m = grid.length; int n = grid[0].length; long[][][] dp = new long[m][n][2]; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ long min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; if(i==0 && j==0){ min = 1; max = 1; }else{ if(i>0){ min = Math.min(min, dp[i-1][j][0]); max = Math.max(max, dp[i-1][j][1]); } if(j>0){ min = Math.min(min, dp[i][j-1][0]); max = Math.max(max, dp[i][j-1][1]); } } long a = (min*grid[i][j]); long b = (max*grid[i][j]); if(a>b){ dp[i][j][1] = a; dp[i][j][0] = b; }else{ dp[i][j][1] = b; dp[i][j][0] = a; } } } /* for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ System.out.print(Arrays.toString(dp[i][j])); System.out.print(" "); } System.out.println(); } */ if(dp[m-1][n-1][1]>=0) return (int)(dp[m-1][n-1][1]%M); else return -1; } }