Find maximum path sum in a 2D matrix when exactly two left moves are allowed | Python3 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 numpy as np NEW_LINE N = 3 NEW_LINE M = 3 NEW_LINE def findMaxSum ( arr ) : NEW_LINE INDENT sum = 0 ; NEW_LINE b = np . zeros ( ( N , M ) ) ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT b [ i ] [ M - 1 ] = arr [ i ] [ M - 1 ] ; NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( M - 2 , - 1 , - 1 ) : NEW_LINE INDENT b [ i ] [ j ] = arr [ i ] [ j ] + b [ i ] [ j + 1 ] ; NEW_LINE DEDENT DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT sum = max ( sum , b [ i ] [ j ] + b [ i - 1 ] [ j ] ) ; NEW_LINE b [ i ] [ j ] = max ( b [ i ] [ j ] , b [ i - 1 ] [ j ] + arr [ i ] [ j ] ) ; NEW_LINE DEDENT DEDENT return sum ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 3 , 7 , 4 ] , [ 1 , 9 , 6 ] , [ 1 , 7 , 7 ] ] ; NEW_LINE print ( findMaxSum ( arr ) ) ; NEW_LINE DEDENT