Maximize the length of upper boundary formed by placing given N rectangles horizontally or vertically | Function to find maximum length of the upper boundary formed by placing each of the rectangles either horizontally or vertically ; Stores the intermediate transition states ; Place the first rectangle horizontally ; Place the first rectangle vertically ; Place horizontally ; Stores the difference in height of current and previous rectangle ; Take maximum out of two options ; Place Vertically ; Stores the difference in height of current and previous rectangle ; Take maximum out two options ; Print maximum of horizontal or vertical alignment of the last rectangle ; Driver Code
def maxBoundary ( N , V ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 2 ) ] for j in range ( N ) ] NEW_LINE dp [ 0 ] [ 0 ] = V [ 0 ] [ 0 ] NEW_LINE dp [ 0 ] [ 1 ] = V [ 0 ] [ 1 ] NEW_LINE for i in range ( 1 , N , 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = V [ i ] [ 0 ] NEW_LINE height1 = abs ( V [ i - 1 ] [ 1 ] - V [ i ] [ 1 ] ) NEW_LINE height2 = abs ( V [ i - 1 ] [ 0 ] - V [ i ] [ 1 ] ) NEW_LINE dp [ i ] [ 0 ] += max ( height1 + dp [ i - 1 ] [ 0 ] , height2 + dp [ i - 1 ] [ 1 ] ) NEW_LINE dp [ i ] [ 1 ] = V [ i ] [ 1 ] NEW_LINE vertical1 = abs ( V [ i ] [ 0 ] - V [ i - 1 ] [ 1 ] ) ; NEW_LINE vertical2 = abs ( V [ i ] [ 0 ] - V [ i - 1 ] [ 1 ] ) ; NEW_LINE dp [ i ] [ 1 ] += max ( vertical1 + dp [ i - 1 ] [ 0 ] , vertical2 + dp [ i - 1 ] [ 1 ] ) NEW_LINE DEDENT print ( max ( dp [ N - 1 ] [ 0 ] , dp [ N - 1 ] [ 1 ] ) - 1 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE V = [ [ 2 , 5 ] , [ 3 , 8 ] , [ 1 , 10 ] , [ 7 , 14 ] , [ 2 , 5 ] ] NEW_LINE maxBoundary ( N , V ) NEW_LINE DEDENT