What is the Longest Bitonic Subsequence?
The Longest Bitonic Subsequence is the longest subsequence that, keeping the original order, strictly increases for a while, hits a single peak, and then strictly decreases. In short, a "mountain" shape.
Elements don't need to be consecutive — only the order must be preserved. A purely rising or purely falling run still counts as bitonic.
Why Is It a Variation of LIS?
A mountain splits into two parts at its peak:
- •Left of the peak: a strictly increasing run (the rise)
- •Right of the peak: a strictly decreasing run (the fall)
Here is the key observation: the rise is a forward LIS (Longest Increasing Subsequence), and the fall is a backward LIS (an LIS computed on the reversed array). So combining two LIS values gives the bitonic length.
How It Works
Step 1. Compute inc[i] forward — the length of the longest increasing subsequence ending at i.
Step 2. Compute dec[i] backward — the length of the longest decreasing subsequence starting at i (an LIS scanned from the right).
Step 3. Treat each i as the peak and compute inc[i] + dec[i] - 1. The peak is counted on both sides, so subtract 1.
Step 4. The maximum over all i is the answer.
Walking Through an Example
Take the altitude array [1, 5, 2, 8, 4, 3].
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| h | 1 | 5 | 2 | 8 | 4 | 3 |
| inc | 1 | 2 | 2 | 3 | 3 | 3 |
| dec | 1 | 2 | 1 | 3 | 2 | 1 |
| inc+dec-1 | 1 | 3 | 2 | 5 | 4 | 3 |
At peak i=3 (altitude 8), inc=3, dec=3 → 3+3-1=5 is the maximum. The actual sequence is [1, 2, 8, 4, 3] — it rises 1<2<8, then falls 8>4>3.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n²) (two double loops) |
| Space | O(n) (inc, dec arrays) |
If you compute each LIS with an O(n log n) binary search, the whole thing drops to O(n log n). But the O(n²) version makes the "split at the peak" idea much clearer.
Common Mistakes
- •Double-counting the peak: Adding only
inc[i] + dec[i]counts the peak twice. You must subtract 1. - •Equality handling: Because the rise/fall is *strict*, use
<for comparisons. Using<=lets equal values sneak in and breaks the mountain shape. - •Backward direction confusion:
decis the length of the fall going *right* from i. Fill it from the back, but the condition looks for smaller values ahead:h[j] < h[i]withj > i.
See It in Action on AlgoNote
Watch the forward LIS fill the rise, the backward LIS fill the fall, and the two lengths combine at each candidate peak — step by step on AlgoNote. Change the altitude array and see where the peak moves.