Longest Bitonic Subsequence
Implement longestBitonicSubsequence
Given an array of integers, find the length of its longest bitonic subsequence — a run of elements, not necessarily touching in the original array, that strictly climbs for a while and then strictly falls, sharing exactly one peak between the two halves. A subsequence that only climbs, or only falls, still counts as bitonic, since the missing half can simply be empty.
Every element is a candidate for that shared peak. Once an index is fixed as the peak, the problem splits cleanly into two independent, already-familiar pieces: how long an increasing run can end there, coming in from the left, and how long a decreasing run can start there, going out to the right. Both of those are exactly the Longest Increasing Subsequence question — one running forward, one running backward — and adding their two lengths together, minus one for the peak counted in both halves, gives the bitonic length through that particular peak. Checking every possible peak and keeping the best result found answers the whole question.
Example 1:
Input: nums = [1,9,2,8,3,7,2,1]
Output: 6
Example 2:
Input: nums = [1,2,3,4,5]
Output: 5
Example 3:
Input: nums = [3,3,3]
Output: 1
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 12 - ●
-1000 ≤ nums[i] ≤ 1000
nums =
[1, 9, 2, 8, 3, 7, 2, 1]