Longest Bitonic Subsequence

The longest bitonic subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are first sorted in in increasing order, then in decreasing order, and the subsequence is as long as possible.

The problem differs from problem of finding longest Bitonic subarray. Unlike subarrays, subsequences are not required to occupy consecutive positions within the original sequences.
 

For example, Longest Bitonic Subsequence of sequence [4, 2, 5, 9, 7, 6, 10, 3, 1] is
[4, 5, 9, 7, 6, 3, 1]

For sequences sorted in increasing or decreasing order, the output is same as the input sequence. i.e.

[1, 2, 3, 4, 5] —> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] —> [5, 4, 3, 2, 1]

 


 

The idea is to maintain two arrays I[] and D[]

  • I[i] stores the length of the longest increasing subsequence ending with arr[i]
  • D[i] stores the length of the longest decreasing subsequence starting from arr[i]

Finally, length of Longest Bitonic Subsequence is maximum among all (I[i] + D[i] – 1).


For example, consider sequence [4, 2, 5, 9, 7, 6, 10, 3, 1]. The contents of LIS and LDS array are –

         |  I[i] |  D[i] |
(i = 0)  |   1   |   3   |
(i = 1)  |   1   |   2   |
(i = 2)  |   2   |   3   |
(i = 3)  |   3   |   5   |

(i = 4)  |   3   |   4   |
(i = 5)  |   3   |   3   |
(i = 6)  |   4   |   3   |
(i = 7)  |   2   |   3   |
(i = 8)  |   1   |   1   |

 
Longest Bitonic Subsequence length is 7 [4, 5, 9, 7, 6, 3, 1]
Longest Bitonic Subsequence is formed by (I[3] + D[3] – 1)

 
C++ implementation –
 

Download   Run Code

Output:

Length of Longest Bitonic Subsequence is 7

 


 

How to print LBS?

The idea remains the same except instead of storing the length of the LIS and LDS, we store LIS and LDS itself.


For example, consider sequence [4, 2, 5, 9, 7, 6, 10, 3, 1]. The contents of LIS and LDS vector are

         |   I[i]       |  D[i]
(i = 0)  |   4          |  4 3 1
(i = 1)  |   2          |  2 1
(i = 2)  |   4 5        |  5 3 1
(i = 3)  |   4 5 9      |  9 7 6 3 1

(i = 4)  |   4 5 7      |  7 6 3 1
(i = 5)  |   4 5 6      |  6 3 1
(i = 6)  |   4 5 9 10   |  10 3 1
(i = 7)  |   2 3        |  3 1
(i = 8)  |   1          |  1

 
Longest Bitonic Subsequence is [4, 5, 9, 7, 6, 3, 1] and is formed by I[3] + D[3].

 
C++ implementation –
 

Download   Run Code

Output:

Longest Bitonic Subsequence is
4 5 9 7 6 3 1

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂