Maximum non | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxProductPath ( vector < vector < int > > grid ) { int n = grid . size ( ) ; int m = grid [ 0 ] . size ( ) ; vector < vector < int > > maxPath ( n , vector < int > ( m , 0 ) ) ; vector < vector < int > > minPath ( n , vector < int > ( m , 0 ) ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { int mn = INT_MAX ; int mx = INT_MIN ; if ( i == 0 and j == 0 ) { mx = grid [ i ] [ j ] ; mn = grid [ i ] [ j ] ; } if ( i > 0 ) { int tempmx = max ( ( maxPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) , ( minPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) ) ; mx = max ( mx , tempmx ) ; int tempmn = min ( ( maxPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) , ( minPath [ i - 1 ] [ j ] * grid [ i ] [ j ] ) ) ; mn = min ( mn , tempmn ) ; } if ( j > 0 ) { int tempmx = max ( ( maxPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) , ( minPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) ) ; mx = max ( mx , tempmx ) ; int tempmn = min ( ( maxPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) , ( minPath [ i ] [ j - 1 ] * grid [ i ] [ j ] ) ) ; mn = 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 ] ) ; } int main ( ) { vector < vector < int > > mat = { { 1 , -2 , 1 } , { 1 , -2 , 1 } , { 3 , -4 , 1 } } ; cout << ( maxProductPath ( mat ) ) ; }