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
def maxSum ( V , n , m ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT aux = [ ] NEW_LINE for j in range ( m ) : NEW_LINE INDENT aux . append ( [ V [ i + 1 ] [ j ] , j ] ) NEW_LINE DEDENT aux = sorted ( aux ) NEW_LINE aux = aux [ : : - 1 ] NEW_LINE for j in range ( m ) : NEW_LINE INDENT for k in range ( m ) : NEW_LINE INDENT if ( aux [ k ] [ 1 ] - j == 0 or abs ( aux [ k ] [ 1 ] - j ) > 1 ) : NEW_LINE INDENT V [ i ] [ j ] += aux [ k ] [ 0 ] NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( m ) : NEW_LINE INDENT ans = max ( ans , V [ 0 ] [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT V = [ [ 1 , 2 , 3 , 4 ] , [ 8 , 7 , 6 , 5 ] , [ 10 , 11 , 12 , 13 ] ] NEW_LINE n = len ( V ) NEW_LINE m = len ( V [ 0 ] ) NEW_LINE print ( maxSum ( V , n , m ) ) NEW_LINE DEDENT