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)(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)(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)(15, 12, 5, 3, 2, 1).

Let’s say you have the following array:

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

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

Constraints:

  • 11\leq nums.length 3×103\leq 3\times10^3
  • 11\leq nums[i] 104\leq 10^4

Examples

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