Maximize the length of upper boundary formed by placing given N rectangles horizontally or vertically | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maxBoundary ( int N , vector < pair < int , int > > V ) { int dp [ N ] [ 2 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 0 ] [ 0 ] = V [ 0 ] . first ; dp [ 0 ] [ 1 ] = V [ 0 ] . second ; for ( int i = 1 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = V [ i ] . first ; int height1 = abs ( V [ i - 1 ] . second - V [ i ] . second ) ; int height2 = abs ( V [ i - 1 ] . first - V [ i ] . second ) ; dp [ i ] [ 0 ] += max ( height1 + dp [ i - 1 ] [ 0 ] , height2 + dp [ i - 1 ] [ 1 ] ) ; dp [ i ] [ 1 ] = V [ i ] . second ; int vertical1 = abs ( V [ i ] . first - V [ i - 1 ] . second ) ; int vertical2 = abs ( V [ i ] . first - V [ i - 1 ] . first ) ; dp [ i ] [ 1 ] += max ( vertical1 + dp [ i - 1 ] [ 0 ] , vertical2 + dp [ i - 1 ] [ 1 ] ) ; } cout << max ( dp [ N - 1 ] [ 0 ] , dp [ N - 1 ] [ 1 ] ) ; } int main ( ) { int N = 5 ; vector < pair < int , int > > V = { { 2 , 5 } , { 3 , 8 } , { 1 , 10 } , { 7 , 14 } , { 2 , 5 } } ; maxBoundary ( N , V ) ; return 0 ; }