Longest Bitonic Subsequence
HardDynamic ProgrammingArray
Description
Given an array, return the length of the longest subsequence that first strictly increases then strictly decreases. A purely increasing or purely decreasing sequence also qualifies.
Examples
Input:
nums = [1,11,2,10,4,5,2,1]Output:
6Explanation:
Subsequence 1,2,10,4,2,1 (or 1,2,4,5,2,1) has length 6 and is bitonic.
Input:
nums = [12,11,40,5,3,1]Output:
5Explanation:
Subsequence 12,40,5,3,1 (or 11,40,5,3,1) is bitonic with length 5.
Input:
nums = [1,2,3,4]Output:
4Explanation:
A strictly increasing sequence is considered bitonic, so the answer equals the array length of 4.
Constraints
- •
1 ≤ nums.length ≤ 1000 - •
-10⁹ ≤ nums[i] ≤ 10⁹