Collect maximum points in a grid using two traversals | A Memoization based program to find maximum collection using two traversals of a grid ; checks whether a given input is valid or not ; Driver function to collect Math . max value ; if P1 or P2 is at an invalid cell ; if both traversals reach their destinations ; If both traversals are at last row but not at their destination ; If subproblem is already solved ; Initialize answer for this subproblem ; this variable is used to store gain of current cell ( s ) ; Recur for all possible cases , then store and return the one with max value ; This is mainly a wrapper over recursive function getMaxUtil ( ) . This function creates a table for memoization and calls getMaxUtil ( ) ; Create a memoization table and initialize all entries as - 1 ; Calculation maximum value using memoization based function getMaxUtil ( ) ; Driver code
class GFG { static final int R = 5 ; static final int C = 4 ; static boolean isValid ( int x , int y1 , int y2 ) { return ( x >= 0 && x < R && y1 >= 0 && y1 < C && y2 >= 0 && y2 < C ) ; } static int getMaxUtil ( int arr [ ] [ ] , int mem [ ] [ ] [ ] , int x , int y1 , int y2 ) { if ( ! isValid ( x , y1 , y2 ) ) return Integer . MIN_VALUE ; if ( x == R - 1 && y1 == 0 && y2 == C - 1 ) return ( y1 == y2 ) ? arr [ x ] [ y1 ] : arr [ x ] [ y1 ] + arr [ x ] [ y2 ] ; if ( x == R - 1 ) return Integer . MIN_VALUE ; if ( mem [ x ] [ y1 ] [ y2 ] != - 1 ) return mem [ x ] [ y1 ] [ y2 ] ; int ans = Integer . MIN_VALUE ; int temp = ( y1 == y2 ) ? arr [ x ] [ y1 ] : arr [ x ] [ y1 ] + arr [ x ] [ y2 ] ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 - 1 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 + 1 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 - 1 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 + 1 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 - 1 ) ) ; ans = Math . max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 + 1 ) ) ; return ( mem [ x ] [ y1 ] [ y2 ] = ans ) ; } static int geMaxCollection ( int arr [ ] [ ] ) { int [ ] [ ] [ ] mem = new int [ R ] [ C ] [ C ] ; for ( int i = 0 ; i < R ; i ++ ) { for ( int j = 0 ; j < C ; j ++ ) { for ( int l = 0 ; l < C ; l ++ ) mem [ i ] [ j ] [ l ] = - 1 ; } } return getMaxUtil ( arr , mem , 0 , 0 , C - 1 ) ; } public static void main ( String [ ] args ) { int arr [ ] [ ] = { { 3 , 6 , 8 , 2 } , { 5 , 2 , 4 , 3 } , { 1 , 1 , 20 , 10 } , { 1 , 1 , 20 , 10 } , { 1 , 1 , 20 , 10 } , } ; System . out . print ( " Maximum ▁ collection ▁ is ▁ " + geMaxCollection ( arr ) ) ; } }