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 Code
def longLenStrictBitonicSub ( arr , n ) : NEW_LINE INDENT inc , dcr = dict ( ) , dict ( ) NEW_LINE len_inc , len_dcr = [ 0 ] * n , [ 0 ] * n NEW_LINE longLen = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT len = 0 NEW_LINE if inc . get ( arr [ i ] - 1 ) in inc . values ( ) : NEW_LINE INDENT len = inc . get ( arr [ i ] - 1 ) NEW_LINE DEDENT inc [ arr [ i ] ] = len_inc [ i ] = len + 1 NEW_LINE DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT len = 0 NEW_LINE if dcr . get ( arr [ i ] - 1 ) in dcr . values ( ) : NEW_LINE INDENT len = dcr . get ( arr [ i ] - 1 ) NEW_LINE DEDENT dcr [ arr [ i ] ] = len_dcr [ i ] = len + 1 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if longLen < ( len_inc [ i ] + len_dcr [ i ] - 1 ) : NEW_LINE INDENT longLen = len_inc [ i ] + len_dcr [ i ] - 1 NEW_LINE DEDENT DEDENT return longLen NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 5 , 2 , 3 , 4 , 5 , 3 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Longest ▁ length ▁ strict ▁ bitonic ▁ subsequence ▁ = " , longLenStrictBitonicSub ( arr , n ) ) NEW_LINE DEDENT