215. Longest Bitonic Subsequence

Given an array of n integers, find the length of its longest bitonic subsequence - one that strictly increases and then strictly decreases (either the increasing part or the decreasing part may be empty, so a purely increasing or purely decreasing subsequence also qualifies).

Input: The first line contains an integer n. The second line contains n space-separated integers, the array. Output: Print a single integer - the length of the longest bitonic subsequence.

1 <= n <= 10^4

A PURELY increasing (or purely decreasing) subsequence is explicitly allowed to qualify as bitonic too (with an empty decreasing, or empty increasing, part) - this problem's own statement clarifies this, an important detail for correctly handling arrays that are already fully sorted in one direction.

Find the length of the longest subsequence that strictly increases and then strictly decreases. Brute force: Try every possible subsequence directly and check if it's bitonic (increases then decreases), taking the longest - this is exponential, impractical for n up to 10^4. Optimised: Since a bitonic sequence's PEAK is some specific index, computing the best increasing run ending at each index and the best decreasing run starting at each index (both standard LIS-family computations) lets you directly combine them at every candidate peak, checking all n possible peaks in the same O(n²) time as computing either array alone.

Compute lis[i] and lds[i] using the patience-sorting style longest-increasing-subsequence algorithm, which maintains a small 'tails' array of the smallest possible tail value for increasing subsequences of each length and uses binary search to find where each new element belongs, run once forward for lis[] and once on the reversed array for lds[]. Then combine them exactly as in the better approach, taking the maximum of lis[i] + lds[i] - 1. This preserves correctness for the same reason as before, but replacing the O(n) inner scan with an O(log n) binary search at each step brings the overall time down substantially. Time: O(n log n) Space: O(n)

Compute an array lis[i] holding the length of the longest strictly increasing subsequence ending at index i, using the standard O(n^2) DP that checks all earlier indices j for each i, and separately compute lds[i] holding the length of the longest strictly decreasing subsequence starting at index i by running the same DP idea from the right end. The answer is the maximum over all i of lis[i] + lds[i] - 1 (subtracting 1 since index i is counted in both). This works because any bitonic subsequence has a single peak, and considering every index as a potential peak while combining the best increasing run into it with the best decreasing run out of it covers every possibility. Time: O(n^2) Space: O(n)

Generate every subsequence of the array and check whether it strictly increases and then strictly decreases (allowing either part to be empty), tracking the longest one that qualifies. This directly checks the bitonic definition against every possible candidate, so it is guaranteed correct, but since the number of subsequences doubles with each additional element, it quickly becomes computationally infeasible. Time: O(2^n) Space: O(n)

1. Compute inc[i] = length of the longest INCREASING subsequence ENDING at i (same as standard LIS). 2. Compute dec[i] = length of the longest DECREASING subsequence STARTING at i (LIS computed on the reversed array, or equivalently scanning right to left). 3. The best bitonic sequence PEAKING at index i has length inc[i]+dec[i]-1 (subtracting 1 since index i itself is counted in both); take the maximum over all i.

Time: O(n²) - computing inc[] and dec[] arrays, each in O(n²) using the standard LIS DP. Space: O(n), for the inc[] and dec[] arrays.

Test a purely increasing array and a purely decreasing array (either the increasing or decreasing half is empty), an array with duplicate values, and n at the upper bound of 10^4.

Be ready to explain why subtracting 1 in inc[i]+dec[i]-1 is necessary - the peak element at index i is counted once in inc[i] and once again in dec[i], so the -1 corrects for this double-counting of the single peak element.