Given an array arr[0 … n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.
A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.
Examples:
Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)
Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)
Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)
Source: Microsoft Interview Question
Solution
This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. Let the input array be arr[] of length n. We need to construct two arrays lis[] and lds[] using Dynamic Programming solution of LIS problem. lis[i] stores the length of the Longest Increasing subsequence ending with arr[i]. lds[i] stores the length of the longest Decreasing subsequence starting from arr[i]. Finally, we need to return the max value of lis[i] + lds[i] – 1 where i is from 0 to n-1.
Following is the implementation of the above Dynamic Programming solution.
Python
# Dynamic Programming implementation of 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] """ def lbs(arr): n = len(arr) # allocate memory for LIS[] and initialize LIS values as 1 # for all indexes lis = [1 for i in range(n+1)] # Compute LIS values from left to right for i in range(1 , n): for j in range(0 , i): if ((arr[i] > arr[j]) and (lis[i] < lis[j] +1)): lis[i] = lis[j] + 1 # allocate memory for LDS and initialize LDS values for # all indexes lds = [1 for i in range(n+1)] # Compute LDS values from right to left for i in reversed(range(n-1)): #loop from n-2 downto 0 for j in reversed(range(i-1 ,n)): #loop from n-1 downto i-1 if(arr[i] > arr[j] and lds[i] < lds[j] + 1): lds[i] = lds[j] + 1 # Return the maximum value of (lis[i] + lds[i] - 1) maximum = lis[0] + lds[0] - 1 for i in range(1 , n): maximum = max((lis[i] + lds[i]-1), maximum) return maximum # Driver program to test the above function arr = [0 , 8 , 4, 12, 2, 10 , 6 , 14 , 1 , 9 , 5 , 13, 3, 11 , 7 , 15] print "Length of LBS is",lbs(arr) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
Output:
Length of LBS is 7
Time Complexity: O(n^2)
Auxiliary Space: O(n)
Please refer complete article on Longest Bitonic Subsequence | DP-15 for more details!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000 neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
