Find maximum sum from top to bottom row with no adjacent diagonal elements | Java implementation to find maximum sum from top to bottom row with no adjacent diagonal elements ; Function to find the maximum path sum from top to bottom row ; Create an auxiliary array of next row with the element and it 's position ; Sort the auxiliary array ; Find maximum from row above to be added to the current element ; Find the maximum element from the next row that can be added to current row element ; Find the maximum sum ; Driver code ; Function to find maximum path
import java . util . * ; import java . lang . * ; import java . io . * ; class GFG { static int maxSum ( int [ ] [ ] V , int n , int m ) { int ans = 0 ; for ( int i = n - 2 ; i >= 0 ; -- i ) { ArrayList < int [ ] > aux = new ArrayList < > ( ) ; for ( int j = 0 ; j < m ; ++ j ) { aux . add ( new int [ ] { V [ i + 1 ] [ j ] , j } ) ; } Collections . sort ( aux , ( a , b ) -> b [ 0 ] - a [ 0 ] ) ; for ( int j = 0 ; j < m ; ++ j ) { for ( int k = 0 ; k < m ; ++ k ) { if ( aux . get ( k ) [ 1 ] - j == 0 || Math . abs ( aux . get ( k ) [ 1 ] - j ) > 1 ) { V [ i ] [ j ] += aux . get ( k ) [ 0 ] ; break ; } } } } for ( int i = 0 ; i < m ; ++ i ) { ans = Math . max ( ans , V [ 0 ] [ i ] ) ; } return ans ; } public static void main ( String [ ] args ) { int [ ] [ ] V = { { 1 , 2 , 3 , 4 } , { 8 , 7 , 6 , 5 } , { 10 , 11 , 12 , 13 } } ; int n = V . length ; int m = V [ 0 ] . length ; System . out . println ( maxSum ( V , n , m ) ) ; } }