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
using System ; using System . Collections . Generic ; class GFG { static void maxBoundary ( int N , List < Tuple < int , int > > V ) { int [ , ] dp = new int [ N , 2 ] ; dp [ 0 , 0 ] = V [ 0 ] . Item1 ; dp [ 0 , 1 ] = V [ 0 ] . Item2 ; for ( int i = 1 ; i < N ; i ++ ) { dp [ i , 0 ] = V [ i ] . Item1 ; int height1 = Math . Abs ( V [ i - 1 ] . Item2 - V [ i ] . Item2 ) ; int height2 = Math . Abs ( V [ i - 1 ] . Item1 - V [ i ] . Item2 ) ; dp [ i , 0 ] += Math . Max ( height1 + dp [ i - 1 , 0 ] , height2 + dp [ i - 1 , 1 ] ) ; dp [ i , 1 ] = V [ i ] . Item2 ; int vertical1 = Math . Abs ( V [ i ] . Item1 - V [ i - 1 ] . Item2 ) ; int vertical2 = Math . Abs ( V [ i ] . Item1 - V [ i - 1 ] . Item1 ) ; dp [ i , 1 ] += Math . Max ( vertical1 + dp [ i - 1 , 0 ] , vertical2 + dp [ i - 1 , 1 ] ) ; } Console . WriteLine ( Math . Max ( dp [ N - 1 , 0 ] , dp [ N - 1 , 1 ] ) ) ; } static void Main ( ) { int N = 5 ; List < Tuple < int , int > > V = new List < Tuple < int , int > > ( ) ; V . Add ( new Tuple < int , int > ( 2 , 5 ) ) ; V . Add ( new Tuple < int , int > ( 3 , 8 ) ) ; V . Add ( new Tuple < int , int > ( 1 , 10 ) ) ; V . Add ( new Tuple < int , int > ( 7 , 14 ) ) ; V . Add ( new Tuple < int , int > ( 2 , 5 ) ) ; maxBoundary ( N , V ) ; } }