Maximize the diamonds by choosing different colour diamonds from adjacent boxes | Function to return the maximized value ; Number of rows and columns ; Creating the Dp array ; Populating the first column ; Iterating over all the rows ; Getting the ( i - 1 ) th max value ; Adding it to the current cell ; Getting the max sum from the last column ; Driver code ; Columns are indexed 1 - based
def maxSum ( arr ) : NEW_LINE INDENT m = len ( arr ) NEW_LINE n = len ( arr [ 0 ] ) - 1 NEW_LINE dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( m ) ] NEW_LINE for i in range ( 1 , m , 1 ) : NEW_LINE INDENT dp [ i ] [ 1 ] = arr [ i ] [ 1 ] NEW_LINE DEDENT for i in range ( 1 , n + 1 , 1 ) : NEW_LINE INDENT for j in range ( 1 , m , 1 ) : NEW_LINE INDENT mx = 0 NEW_LINE for k in range ( 1 , m , 1 ) : NEW_LINE INDENT if ( k != j ) : NEW_LINE INDENT if ( dp [ k ] [ i - 1 ] > mx ) : NEW_LINE INDENT mx = dp [ k ] [ i - 1 ] NEW_LINE DEDENT DEDENT DEDENT if ( mx and arr [ j ] [ i ] ) : NEW_LINE INDENT dp [ j ] [ i ] = arr [ j ] [ i ] + mx NEW_LINE DEDENT DEDENT DEDENT ans = - 1 NEW_LINE for i in range ( 1 , m , 1 ) : NEW_LINE INDENT if ( dp [ i ] [ n ] ) : NEW_LINE INDENT ans = max ( ans , dp [ i ] [ n ] ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 0 , 0 , 0 , 0 , 0 ] , [ 0 , 10 , 2 , 20 , 0 ] , [ 0 , 0 , 0 , 5 , 0 ] , [ 0 , 0 , 0 , 0 , 6 ] , [ 0 , 4 , 0 , 11 , 5 ] , [ 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 ] ] NEW_LINE print ( maxSum ( arr ) ) NEW_LINE DEDENT