Longest Bitonic Subsequence
Let's solve the Longest Bitonic Subsequence problem using Dynamic Programming.
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 \times 10^3$  $1\leq$
nums[i]
$\leq 10^4$
Examples
Level up your interview prep. Join Educative to access 70+ handson prep courses.