The problem of finding the Longest Bitonic Sequence (the longest sequence that either first decreases then increases, or first increases then decreases) is well known. We can just do DP, keep for each prefix the longest increasing and decreasing subsequence and also for each suffix. Then just loop through all possible "middle" indices (indices where the sequence transitions from increasing to decreasing or the other way around) and test in that way. The complexity would be O(NlogN + N) (NlogN for each DP, test N center indices) I think.

But I was wondering, whaf is we are given queries that ask for the LBS in a subarray? As far as I know, this has not been in any contest I can find online. I thought we could use a Segment Tree to do this, but I don't know what we'd need to maintain in the nodes. I think we would need to maintain the LIS and LDS (longest increasing/decreasing subsequences) ending at each index as well as the longest bitonic subsequence ending at each index. But this would make queries O(N), which I don't think is good enough. Is there another way to do this?

EDIT: Actually, queries would be O(N^2) I think. My idea is like, for left and right subarrays to be merged, for each number in the right subarray loop over all indices in the left subarray to see if you can append that number to another sequence.