Find maximum sum from top to bottom row with no adjacent diagonal elements | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSum ( vector < vector < int > > & V , int n , int m ) { int ans = 0 ; for ( int i = n - 2 ; i >= 0 ; -- i ) { vector < pair < int , int > > aux ; for ( int j = 0 ; j < m ; ++ j ) { aux . push_back ( { V [ i + 1 ] [ j ] , j } ) ; } sort ( aux . begin ( ) , aux . end ( ) ) ; reverse ( aux . begin ( ) , aux . end ( ) ) ; for ( int j = 0 ; j < m ; ++ j ) { for ( int k = 0 ; k < m ; ++ k ) { if ( aux [ k ] . second - j == 0 || abs ( aux [ k ] . second - j ) > 1 ) { V [ i ] [ j ] += aux [ k ] . first ; break ; } } } } for ( int i = 0 ; i < m ; ++ i ) { ans = max ( ans , V [ 0 ] [ i ] ) ; } return ans ; } int main ( ) { vector < vector < int > > V { { 1 , 2 , 3 , 4 } , { 8 , 7 , 6 , 5 } , { 10 , 11 , 12 , 13 } } ; int n = V . size ( ) ; int m = V [ 0 ] . size ( ) ; cout << maxSum ( V , n , m ) ; return 0 ; }