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, .
-
It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example, .
-
It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example, .
Let’s say you have the following array:
The longest bitonic subsequence from this array is , and the length of this subsequence is .
Constraints:
-
nums.length
nums[i]
Examples
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.