Longest Bitonic Subsequence | DP | Dynamic Programming implementation in Java for longest bitonic subsequence problem ; lbs ( ) returns the length of the Longest Bitonic Subsequence in arr [ ] of size n . The function mainly creates two temporary arrays lis [ ] and lds [ ] and returns the maximum lis [ i ] + lds [ i ] - 1. lis [ i ] == > Longest Increasing subsequence ending with arr [ i ] lds [ i ] == > Longest decreasing subsequence starting with arr [ i ] ; Allocate memory for LIS [ ] and initialize LIS values as 1 for all indexes ; Compute LIS values from left to right ; Allocate memory for lds and initialize LDS values for all indexes ; Compute LDS values from right to left ; Return the maximum value of lis [ i ] + lds [ i ] - 1 ; Driver code
import java . util . * ; import java . lang . * ; import java . io . * ; class LBS { static int lbs ( int arr [ ] , int n ) { int i , j ; int [ ] lis = new int [ n ] ; for ( i = 0 ; i < n ; i ++ ) lis [ i ] = 1 ; for ( i = 1 ; i < n ; i ++ ) for ( j = 0 ; j < i ; j ++ ) if ( arr [ i ] > arr [ j ] && lis [ i ] < lis [ j ] + 1 ) lis [ i ] = lis [ j ] + 1 ; int [ ] lds = new int [ n ] ; for ( i = 0 ; i < n ; i ++ ) lds [ i ] = 1 ; for ( i = n - 2 ; i >= 0 ; i -- ) for ( j = n - 1 ; j > i ; j -- ) if ( arr [ i ] > arr [ j ] && lds [ i ] < lds [ j ] + 1 ) lds [ i ] = lds [ j ] + 1 ; int max = lis [ 0 ] + lds [ 0 ] - 1 ; for ( i = 1 ; i < n ; i ++ ) if ( lis [ i ] + lds [ i ] - 1 > max ) max = lis [ i ] + lds [ i ] - 1 ; return max ; } public static void main ( String [ ] args ) { int arr [ ] = { 0 , 8 , 4 , 12 , 2 , 10 , 6 , 14 , 1 , 9 , 5 , 13 , 3 , 11 , 7 , 15 } ; int n = arr . length ; System . out . println ( " Length ▁ of ▁ LBS ▁ is ▁ " + lbs ( arr , n ) ) ; } }