Skip to content

Latest commit

 

History

History
107 lines (94 loc) · 3.4 KB

1594. Maximum Non Negative Product in a Matrix.md

File metadata and controls

107 lines (94 loc) · 3.4 KB

1594. Maximum Non Negative Product in a Matrix

the third one in Weekly Contest 207.

Difficulty : Medium

Related Topics : Dynamic Programming、Greedy

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 10^9 + 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

Solution

  • mine
    • Java
      • DP Runtime: 1 ms, faster than 100.00%, Memory Usage: 39.4 MB, less than 25.00% of Java online submissions 
        // O(r * c)time
// O(r * c)space
public int maxProductPath(int[][] grid) {
    int r = grid.length, c = grid[0].length;
    long[][][] dp = new long[r][c][2];
    int mod = 1000000007;
    dp[0][0][0] = dp[0][0][1] = grid[0][0];
    for (int i = 1; i < r; i++) {
        dp[i][0][0] = Math.max(grid[i][0] * dp[i - 1][0][0], grid[i][0] * dp[i - 1][0][1]);
        dp[i][0][1] = Math.min(grid[i][0] * dp[i - 1][0][0], grid[i][0] * dp[i - 1][0][1]);

    }
    for (int i = 1; i < c; i++) {
        dp[0][i][0] = Math.max(grid[0][i] * dp[0][i - 1][0], grid[0][i] * dp[0][i - 1][1]);
        dp[0][i][1] = Math.min(grid[0][i] * dp[0][i - 1][0], grid[0][i] * dp[0][i - 1][1]);
    }
    for(int i = 1; i < r; i++){
        for(int j = 1; j < c; j++){
            long a = dp[i - 1][j][0] * grid[i][j];
            long b = dp[i - 1][j][1] * grid[i][j];
            long m = dp[i][j - 1][0] * grid[i][j];
            long n = dp[i][j - 1][1] * grid[i][j];
            long max = Math.max(Math.max(a, b), Math.max(m, n));
            long min = Math.min(Math.min(a, b), Math.min(m, n));
            dp[i][j][0] = max;
            dp[i][j][1] = min;
        }
    }
    long res = dp[r - 1][c - 1][0];
    if(res < 0) return -1;
    return (int)(res % mod);
}