Longest Bitonic Subsequence

Let's solve the Longest Bitonic Subsequence problem using Dynamic Programming.

We'll cover the following

Statement

Suppose you are given an array, nums, containing positive integers. You need to find the length of the longest bitonic subsequence in this array. A bitonic subsequence can be of the following three types:

• It can consist of numbers that are first increasing and then decreasing. For example, $(2, 6, 9, 3, 2)$.

• It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example, $(2, 3, 7, 9)$.

• It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example, $(15, 12, 5, 3, 2, 1)$.

Let’s say you have the following array:

• $[19, 20, 5, 3, 13]$

The longest bitonic subsequence from this array is $(19, 20, 5, 3)$, and the length of this subsequence is $4$.

Constraints:

• $1\leq$ nums.length $\leq 3\times10^3$
• $1\leq$ nums[i] $\leq 10^4$

Examples

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.