# 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 + D – 1)

Below is C++ and Java implementation of the idea:

## C++

Output:

Length of Longest Bitonic Subsequence is 7

## Java

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 + D.

Below is C++ implementation of the idea:

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).     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

Hi,
Can someone please post java code for “Print LBS”. Guest

The inner loops for calculating I & D array can be optimized by reversing the order: i.e. start from i-1 to zero and break when a match is found.
```for i in range(1, len(arr)): for j in range(i-1, -1, -1): if arr[j] < arr[i]: I[i] = I[j] break```