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

For example, the longest bitonic subsequence of a 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 the 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 problem differs from the problem of finding the longest bitonic subarray. Unlike subarrays, subsequences are not required to occupy consecutive positions within the original array.

Practice this problem

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

Finally, the length of longest bitonic subsequence is maximum among all I[i] + D[i] - 1. For example, consider the sequence [4, 2, 5, 9, 7, 6, 10, 3, 1]. The contents of the 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   |

The longest bitonic subsequence length is 7 [4, 5, 9, 7, 6, 3, 1]. The longest bitonic subsequence is formed by I[3] + D[3] - 1.

Following is the C++, Java, and Python implementation of the idea:

C++


Download  Run Code

Output:

The length of the longest bitonic subsequence is 7

Java


Download  Run Code

Output:

The length of the longest bitonic subsequence is 7

Python


Download  Run Code

Output:

The length of the 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 the sequence [4, 2, 5, 9, 7, 6, 10, 3, 1]. The contents of the LIS and LDS list 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

The longest bitonic subsequence is [4, 5, 9, 7, 6, 3, 1] and is formed by I[3] + D[3]. Following is the C++, Java, and Python implementation of the idea:

C++


Download  Run Code

Output:

The longest bitonic subsequence is 4 5 9 7 6 3 1

Java


Download  Run Code

Output:

The longest bitonic subsequence is [4, 5, 9][7, 6, 3, 1]

Python


Download  Run Code

Output:

The longest bitonic subsequence is [4, 5, 9][7, 6, 3, 1]

The time complexity of the above solution is O(n2) and requires O(n2) extra space, where n is the size of the given sequence.