Maximize the length of upper boundary formed by placing given N rectangles horizontally or vertically | Java program for the above approach ; Utility class ; 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
import java . util . Vector ; public class GFG { public static class pair { private int first ; private int second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void maxBoundary ( int N , Vector < pair > V ) { int dp [ ] [ ] = new int [ N ] [ 2 ] ; dp [ 0 ] [ 0 ] = V . get ( 0 ) . first ; dp [ 0 ] [ 1 ] = V . get ( 0 ) . second ; for ( int i = 1 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = V . get ( i ) . first ; int height1 = Math . abs ( V . get ( i - 1 ) . second - V . get ( i ) . second ) ; int height2 = Math . abs ( V . get ( i - 1 ) . first - V . get ( i ) . second ) ; dp [ i ] [ 0 ] += Math . max ( height1 + dp [ i - 1 ] [ 0 ] , height2 + dp [ i - 1 ] [ 1 ] ) ; dp [ i ] [ 1 ] = V . get ( i ) . second ; int vertical1 = Math . abs ( V . get ( i ) . first - V . get ( i - 1 ) . second ) ; int vertical2 = Math . abs ( V . get ( i ) . first - V . get ( i - 1 ) . first ) ; dp [ i ] [ 1 ] += Math . max ( vertical1 + dp [ i - 1 ] [ 0 ] , vertical2 + dp [ i - 1 ] [ 1 ] ) ; } System . out . println ( Math . max ( dp [ N - 1 ] [ 0 ] , dp [ N - 1 ] [ 1 ] ) ) ; } public static void main ( String [ ] args ) { int N = 5 ; Vector < pair > V = new Vector < > ( ) ; V . add ( new pair ( 2 , 5 ) ) ; V . add ( new pair ( 3 , 8 ) ) ; V . add ( new pair ( 1 , 10 ) ) ; V . add ( new pair ( 7 , 14 ) ) ; V . add ( new pair ( 2 , 5 ) ) ; maxBoundary ( N , V ) ; } }