Maximum non | Function to find the maximum product from the top left and bottom right cell of the given matrix grid [ ] [ ] ; Store dimension of grid ; Stores maximum product path ; Stores minimum product path ; Traverse the grid and update maxPath and minPath array ; Initialize to inf and - inf ; Base Case ; Calculate for row : ; Update the maximum ; Update the minimum ; Calculate for column : ; Update the maximum ; Update the minimum ; Update maxPath and minPath ; If negative product ; Otherwise ; Given matrix mat [ ] [ ] ; Function Call
def maxProductPath ( grid ) : NEW_LINE INDENT n , m = len ( grid ) , len ( grid [ 0 ] ) NEW_LINE maxPath = [ [ 0 for i in range ( m ) ] for j in range ( n ) ] NEW_LINE minPath = [ [ 0 for i in range ( m ) ] for j in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT mn = float ( " inf " ) NEW_LINE mx = float ( " - inf " ) NEW_LINE if ( i == 0 and j == 0 ) : NEW_LINE INDENT mx = grid [ i ] [ j ] NEW_LINE mn = grid [ i ] [ j ] NEW_LINE DEDENT if i > 0 : NEW_LINE INDENT tempmx = max ( ( maxPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) , ( minPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) ) NEW_LINE mx = max ( mx , tempmx ) NEW_LINE tempmn = min ( ( maxPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) , ( minPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) ) NEW_LINE mn = min ( mn , tempmn ) NEW_LINE DEDENT if ( j > 0 ) : NEW_LINE INDENT tempmx = max ( ( maxPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) , ( minPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) ) NEW_LINE mx = max ( mx , tempmx ) NEW_LINE tempmn = min ( ( maxPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) , ( minPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) ) NEW_LINE mn = min ( mn , tempmn ) NEW_LINE DEDENT maxPath [ i ] [ j ] = mx NEW_LINE minPath [ i ] [ j ] = mn NEW_LINE DEDENT DEDENT if ( maxPath [ n - 1 ] [ m - 1 ] < 0 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return ( maxPath [ n - 1 ] [ m - 1 ] ) NEW_LINE DEDENT DEDENT mat = [ [ 1 , - 2 , 1 ] , [ 1 , - 2 , 1 ] , [ 3 , - 4 , 1 ] ] NEW_LINE print ( maxProductPath ( mat ) ) NEW_LINE