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
Solution: DP
Use two dp arrays,
dp_max[i][j] := max product of matrix[0~i][0~j]
dp_min[i][j] := min product of matrix[0~i][0~j]
Time complexity: O(m*n)
Space complexity: O(m*n)
C++
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 |
// Author: Huahua class Solution { public: int maxProductPath(vector<vector<int>>& grid) { constexpr int kMod = 1e9 + 7; const int m = grid.size(); const int n = grid[0].size(); vector<vector<long>> dp_max(m, vector<long>(n)); vector<vector<long>> dp_min(m, vector<long>(n)); dp_max[0][0] = dp_min[0][0] = grid[0][0]; for (int i = 1; i < m; ++i) dp_max[i][0] = dp_min[i][0] = dp_min[i - 1][0] * grid[i][0]; for (int j = 1; j < n; ++j) dp_max[0][j] = dp_min[0][j] = dp_min[0][j - 1] * grid[0][j]; for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) { if (grid[i][j] >= 0) { dp_max[i][j] = max(dp_max[i - 1][j], dp_max[i][j - 1]) * grid[i][j]; dp_min[i][j] = min(dp_min[i - 1][j], dp_min[i][j - 1]) * grid[i][j]; } else { dp_max[i][j] = min(dp_min[i - 1][j], dp_min[i][j - 1]) * grid[i][j]; dp_min[i][j] = max(dp_max[i - 1][j], dp_max[i][j - 1]) * grid[i][j]; } } return dp_max[m - 1][n - 1] >= 0 ? dp_max[m - 1][n - 1] % kMod : -1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment