Longest Bitonic Subsequence
DP on LIS DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Longest Bitonic Subsequence, Arrays, Subsequences, Dynamic Programming, Longest Increasing Subsequence, Time Complexity, Space Complexity, Loops, Optimal Substructure, Overlapping Subproblems, space complexity, dynamic programming, algorithm design, array traversal, time complexity analysis, Longest Increasing Subsequence (LIS).
Longest Bitonic Subsequence Problem Statement Given an array Arr of length n, find the length of the longest bitonic subsequence. A bitonic subsequence is a subsequence in which the elements first increase up to a certain point (the peak) and then decrease. This includes subsequences that are purely increasing (monotonically increasing) or purely decreasing (monotonically decreasing). For example: [1, 3, 5, 2, 0] is a bitonic subsequence (increases then decreases). [1, 2, 3, 4] is a bitonic subsequence (purely increasing). [5, 4, 3, 2] is a bitonic subsequence (purely decreasing). Input Specification The first line contains an integer n, the length of the array. The second line contains n space separated integers representing the elements of the array Arr. Output Specification Print a single integer, the length of the longest bitonic subsequence. Sample Test Case Input Output Explanation The longest bitonic subsequence is [1, 2, 10, 4, 2, 1], which has a length of 6. Other examples could be [1, 2, 4, 5, 2, 1]. The peak elements are 10 or 5 respectively.