Maximum sum path in a Matrix | No of rows and columns ; Declaring the matrix of maximum 100 rows and 100 columns ; Variable visited is used to keep track of all the visited positions Variable dp is used to store maximum sum till current position ; For storing current sum ; For continuous update of maximum sum required ; Function to Input the matrix of size n * m ; Function to calculate maximum sum of path ; Checking boundary condition ; Checking whether or not ( i , j ) is visited ; Marking ( i , j ) is visited ; Checking whether the position hasn 't  visited the last row or the last column.  Making recursive call for all the possible  moves from the current cell and then adding the  maximum returned by the calls and updating it. ; Checking whether position has reached last row ; If the position is in the last column ; Updating the maximum sum till the current position in the dp ; Returning the updated maximum value ; Driver Code ; Calling the implemented function
class GFG { static final int N = 100 ; static int n , m ; static int a [ ] [ ] = new int [ N ] [ N ] ; static int dp [ ] [ ] = new int [ N ] [ N ] ; static int visited [ ] [ ] = new int [ N ] [ N ] ; static int current_sum = 0 ; static int total_sum = 0 ; static void inputMatrix ( ) { n = 3 ; m = 3 ; a [ 0 ] [ 0 ] = 500 ; a [ 0 ] [ 1 ] = 100 ; a [ 0 ] [ 2 ] = 230 ; a [ 1 ] [ 0 ] = 1000 ; a [ 1 ] [ 1 ] = 300 ; a [ 1 ] [ 2 ] = 100 ; a [ 2 ] [ 0 ] = 200 ; a [ 2 ] [ 1 ] = 1000 ; a [ 2 ] [ 2 ] = 200 ; } static int maximum_sum_path ( int i , int j ) { if ( i == n - 1 && j == m - 1 ) return a [ i ] [ j ] ; if ( visited [ i ] [ j ] != 0 ) return dp [ i ] [ j ] ; visited [ i ] [ j ] = 1 ; int total_sum = 0 ; if ( i < n - 1 & j < m - 1 ) { int current_sum = Math . max ( maximum_sum_path ( i , j + 1 ) , Math . max ( maximum_sum_path ( i + 1 , j + 1 ) , maximum_sum_path ( i + 1 , j ) ) ) ; total_sum = a [ i ] [ j ] + current_sum ; } else if ( i == n - 1 ) total_sum = a [ i ] [ j ] + maximum_sum_path ( i , j + 1 ) ; else total_sum = a [ i ] [ j ] + maximum_sum_path ( i + 1 , j ) ; dp [ i ] [ j ] = total_sum ; return total_sum ; } public static void main ( String [ ] args ) { inputMatrix ( ) ; int maximum_sum = maximum_sum_path ( 0 , 0 ) ; System . out . println ( maximum_sum ) ; } }