Find maximum path sum in a 2D matrix when exactly two left moves are allowed | Java program to find maximum path sum in a 2D matrix when exactly two left moves are allowed ; Function to return the maximum path sum ; Copy last column i . e . starting and ending columns in another array ; Calculate suffix sum in each row ; Select the path we are going to follow ; Driver Code
import java . io . * ; class GFG { static int N = 3 ; static int M = 3 ; static int findMaxSum ( int arr [ ] [ ] ) { int sum = 0 ; int [ ] [ ] b = new int [ N ] [ M ] ; for ( int i = 0 ; i < N ; i ++ ) { b [ i ] [ M - 1 ] = arr [ i ] [ M - 1 ] ; } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = M - 2 ; j >= 0 ; j -- ) { b [ i ] [ j ] = arr [ i ] [ j ] + b [ i ] [ j + 1 ] ; } } for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { sum = Math . max ( sum , b [ i ] [ j ] + b [ i - 1 ] [ j ] ) ; b [ i ] [ j ] = Math . max ( b [ i ] [ j ] , b [ i - 1 ] [ j ] + arr [ i ] [ j ] ) ; } } return sum ; } public static void main ( String [ ] args ) { int arr [ ] [ ] = { { 3 , 7 , 4 } , { 1 , 9 , 6 } , { 1 , 7 , 7 } } ; System . out . println ( findMaxSum ( arr ) ) ; } }