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

Difficulty: interview

Starter code:

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        if (rows == 0):
            return -1
        
        cols = len(grid[0])
        if (cols == 0):
            return -1
        
        dp = [(1,1)] * cols
        for r, col in enumerate(grid):
            for c, item in enumerate(col):
                if (r == 0 and c == 0):
                    dp[c] = (item, item)
                elif (r == 0):
                    dp[c] = (dp[c-1][0] * item, dp[c-1][1]* item)
                elif (c == 0):
                    dp[c] = (dp[c][0] * item, dp[c][1]* item)
                else:
                    candidate_1 = dp[c-1][0] * item
                    candidate_2 = dp[c-1][1]* item
                    candidate_3 = dp[c][0] * item
                    candidate_4 = dp[c][1]* item
                    
                    m = min(candidate_1, candidate_2, candidate_3, candidate_4)
                    M = max(candidate_1, candidate_2, candidate_3, candidate_4)
                    
                    dp[c] = (m, M)
                    
        if (dp[cols-1][1] >= 0):
            return dp[cols-1][1] % (10**9+7)
        else:
            return -1

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        if (rows == 0):
            return -1
        
        cols = len(grid[0])
        if (cols == 0):
            return -1
        
        dp = [(1,1)] * cols
        
        for r, col in enumerate(grid):
            for c, item in enumerate(col):
                if (r == 0 and c == 0):
                    dp[c] = (item, item)
                elif (r == 0):
                    dp[c] = (dp[c-1][0]*item, dp[c-1][1] * item)
                elif (c == 0):
                    dp[c] = (dp[c][0]*item, dp[c][1] * item)
                else:
                    c1 = dp[c-1][0]*item
                    c2 = dp[c-1][1] * item
                    c3 = dp[c][0]*item
                    c4 = dp[c][1] * item
                    
                    m = min( dp[c-1][0]*item, dp[c-1][1] * item,dp[c][0]*item,  dp[c][1] * item)
                    M = max(dp[c-1][0]*item, dp[c-1][1] * item,dp[c][0]*item,  dp[c][1] * item)
                    dp[c] = (m, M)
                    
        
        if (dp[cols-1][1] >= 0):
            return (dp[cols-1][1] % (10**9 + 7))
        else:
            return -1