Longest Bitonic Subsequence - Two Passes

Compute two arrays: $lis[i]$ = length of LIS ending at index $i$ (standard LIS) $lds[i]$ = length of longest decreasing subsequence starting at index $i$ To get $lds$, run LIS from right to left.

The longest bitonic subsequence using $i$ as peak has length $lis[i] + lds[i] - 1$ (subtract 1 because $i$ is counted twice). The answer is $\max(lis[i] + lds[i] - 1)$ for all $i$.