Maximum non | Java program for the above approach ; 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 ; Driver Code ; Given matrix mat [ ] [ ] ; Function Call
import java . io . * ; class GFG { static int maxProductPath ( int [ ] [ ] grid ) { int n = grid . length ; int m = grid [ 0 ] . length ; int [ ] [ ] maxPath = new int [ n ] [ m ] ; int [ ] [ ] minPath = new int [ n ] [ m ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { int mn = Integer . MAX_VALUE ; int mx = Integer . MIN_VALUE ; if ( i == 0 && j == 0 ) { mx = grid [ i ] [ j ] ; mn = grid [ i ] [ j ] ; } if ( i > 0 ) { int tempmx = Math . max ( ( maxPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) , ( minPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) ) ; mx = Math . max ( mx , tempmx ) ; int tempmn = Math . min ( ( maxPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) , ( minPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) ) ; mn = Math . min ( mn , tempmn ) ; } if ( j > 0 ) { int tempmx = Math . max ( ( maxPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) , ( minPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) ) ; mx = Math . max ( mx , tempmx ) ; int tempmn = Math . min ( ( maxPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) , ( minPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) ) ; mn = Math . min ( mn , tempmn ) ; } maxPath [ i ] [ j ] = mx ; minPath [ i ] [ j ] = mn ; } } if ( maxPath [ n - 1 ] [ m - 1 ] < 0 ) { return - 1 ; } else { return ( maxPath [ n - 1 ] [ m - 1 ] ) ; } } public static void main ( String [ ] args ) { int [ ] [ ] mat = { { 1 , - 2 , 1 } , { 1 , - 2 , 1 } , { 3 , - 4 , 1 } } ; System . out . println ( maxProductPath ( mat ) ) ; } }