Length of longest strict bitonic subsequence | function to find length of longest strict bitonic subsequence ; hash table to map the array element with the length of the longest subsequence of which it is a part of and is the last / first element of that subsequence ; arrays to store the length of increasing and decreasing subsequences which end at them or start from them ; to store the length of longest strict bitonic subsequence ; traverse the array elements from left to right ; initialize current length for element arr [ i ] as 0 ; if ' arr [ i ] -1' is in ' inc ' ; update arr [ i ] subsequence length in ' inc ' and in len_inc [ ] ; traverse the array elements from right to left ; initialize current length for element arr [ i ] as 0 ; if ' arr [ i ] -1' is in ' dcr ' ; update arr [ i ] subsequence length in ' dcr ' and in len_dcr [ ] ; calculating the length of all the strict bitonic subsequence ; required longest length strict bitonic subsequence ; Driver program to test above
function longLenStrictBitonicSub ( arr , n ) { var inc = new Map ( ) , dcr = new Map ( ) ; var len_inc = Array ( n ) , len_dcr = Array ( n ) ; var longLen = 0 ; for ( var i = 0 ; i < n ; i ++ ) { var len = 0 ; if ( inc . has ( arr [ i ] - 1 ) ) len = inc . get ( arr [ i ] - 1 ) ; len_inc [ i ] = len + 1 ; inc . set ( arr [ i ] , len_inc [ i ] ) ; } for ( var i = n - 1 ; i >= 0 ; i -- ) { var len = 0 ; if ( dcr . has ( arr [ i ] - 1 ) ) len = dcr . get ( arr [ i ] - 1 ) ; len_dcr [ i ] = len + 1 ; dcr . set ( arr [ i ] , len_dcr [ i ] ) ; } for ( var i = 0 ; i < n ; i ++ ) if ( longLen < ( len_inc [ i ] + len_dcr [ i ] - 1 ) ) longLen = len_inc [ i ] + len_dcr [ i ] - 1 ; return longLen ; } var arr = [ 1 , 5 , 2 , 3 , 4 , 5 , 3 , 2 ] ; var n = arr . length ; document . write ( " " + longLenStrictBitonicSub ( arr , n ) ) ;