Longest Bitonic Subsequence

Longest Bitonic Subsequence (LBS) reduces to two independent Longest Increasing Subsequence (LIS) sweeps — one run left-to-right computing the best increasing run ending at each index, one run right-to-left computing the best decreasing run starting at each index — because any bitonic sequence has exactly one peak, and once you fix that peak the increasing prefix and decreasing suffix are independent optimization problems that can be solved with plain LIS.

Recognize the pattern

• The phrase "increases then decreases" (or "valley then peak reversed", mountain array) — one direction change allowed, at an unknown index.
• You need a subsequence (skip elements freely), not a contiguous subarray — that's what makes it LIS-shaped rather than a sliding-window problem.
• The answer must combine a prefix property and a suffix property around every candidate index — a strong signal to precompute two arrays (one forward pass, one backward pass) and combine them index-by-index.

Brute force → optimal

Brute force: for every pair of indices (peak position implicit), try all 2ⁿ subsequences and check whether each is bitonic. Cost: O(2ⁿ · n) time, O(1) extra space beyond recursion — completely infeasible past n≈20.

Optimal (DP): compute LIS[i] = length of the longest increasing subsequence ending at index i (standard O(n²) LIS DP scanning left to right), and LDS[i] = length of the longest decreasing subsequence starting at index i (the same DP run right to left). Then for every index i treated as the peak, the bitonic length through it is LIS[i] + LDS[i] - 1 (the peak element is counted in both arrays, so subtract the duplicate). The answer is the max over all i. Cost: O(n²) time, O(n) space — the two DP tables.

Complexity, derived

Computing LIS[i] for a single i scans all j < i and does O(1) work per j, so filling the whole LIS table is Σ i for i=0..n-1 = O(n²) comparisons. The LDS pass is symmetric: O(n²). Combining the two arrays and taking the max is one O(n) pass. Total time = O(n²) + O(n²) + O(n) = O(n²). Space is two length-n arrays for LIS and LDS = O(n) (no recursion stack needed since both DPs are iterative).

If interview pressure demands better, each LIS/LDS pass can be done in O(n log n) with patience sorting (binary search over tails), giving O(n log n) time overall, but you then lose the ability to trivially reconstruct the actual subsequence without extra bookkeeping — most interview answers stop at O(n²) since it is simple and correct.

Traced example

Array: [4, 2, 3, 6, 10, 1, 12] (indices 0..6).

Check LDS[0] by hand: scanning right to left from index 0, the longest decreasing run starting at value 4 is 4,3,1 (indices 0,2,5) or 4,2,1 (indices 0,1,5) — both length 3, so LDS[0]=3, not 2.

Max is 5, tied at two peaks. At i=4 (peak value 10): increasing prefix is 2,3,6,10 (indices 1,2,3,4, length 4 — index 0's value 4 is skipped because 4 is not less than 2), decreasing suffix from the peak is 10,1 (indices 4,5, length 2). Combined, subtracting the shared peak: {2,3,6,10,1}, length 5. At i=6 (peak value 12): the same increasing chain extends one step further, 2,3,6,10,12 (indices 1,2,3,4,6, length 5), and LDS[6]=1 because nothing to the right of index 6 is smaller — the decreasing suffix is just the peak itself. So the bitonic sequence here is the purely increasing run {2,3,6,10,12}, which is a degenerate bitonic shape (decreasing part of length 1). This is exactly why the algorithm must scan the max over all i rather than stop at the first hit: a pure increasing (or pure decreasing) run can tie the true bitonic optimum.

Java implementation

import java.util.Arrays;

class LongestBitonicSubsequence {
    static int lbs(int[] arr) {
        int n = arr.length;
        int[] lis = new int[n];
        int[] lds = new int[n];
        Arrays.fill(lis, 1);
        Arrays.fill(lds, 1);

        // forward pass: longest increasing run ending at i
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (arr[j] < arr[i] && lis[j] + 1 > lis[i])
                    lis[i] = lis[j] + 1;

        // backward pass: longest decreasing run starting at i
        for (int i = n - 2; i >= 0; i--)
            for (int j = n - 1; j > i; j--)
                if (arr[j] < arr[i] && lds[j] + 1 > lds[i])
                    lds[i] = lds[j] + 1;

        int max = 0;
        for (int i = 0; i < n; i++)
            max = Math.max(max, lis[i] + lds[i] - 1);
        return max;
    }
}

Pitfalls

• Forgetting to subtract 1 in LIS[i] + LDS[i] - 1 double-counts the peak element.
• Requiring the peak to have both a real increasing prefix and a real decreasing suffix (LIS[i]>1 and LDS[i]>1) when the problem demands a strict bitonic shape rather than allowing pure-increasing or pure-decreasing as degenerate bitonic — check the problem's exact definition before filtering (see i=6 above, where LDS[6]=1 makes the sequence purely increasing).
• Using strict < everywhere when the array has duplicates can silently break both LIS and LDS on flat runs — clarify whether equal adjacent values are allowed on either side.
• Trying to do LIS and LDS in a single forward pass — the decreasing suffix genuinely needs information from the right side of the array, so a second pass (or one pass over the reversed array) is unavoidable.

When to use / when not — trade-offs

Use this two-pass LIS/LDS combination whenever a subsequence problem has a single "turning point" (bitonic arrays, mountain arrays, max sum increasing-then-decreasing). It is simple, O(n²) is easy to prove correct, and reconstructing the actual subsequence is straightforward by walking predecessor pointers.

Alternative — patience-sorting LIS (O(n log n)) run twice: faster asymptotically, and worth it when n is large (10⁵+), but it only gives you the length arrays directly; recovering the exact bitonic subsequence needs extra parent-pointer bookkeeping on top of the binary-search tails array, adding implementation complexity. For typical interview-size inputs, the O(n²) DP is the better trade-off between speed of writing correct code and runtime.

Takeaways

• Bitonic = one peak; split into independent LIS-forward and LIS-backward (i.e., LDS) sub-problems.
• Combine at every index with LIS[i] + LDS[i] - 1, take the max — the -1 removes the double-counted peak.
• O(n²) time / O(n) space with plain DP; O(n log n) is possible but complicates subsequence reconstruction.

Recall: Why must the peak's LIS and LDS values be computed as full independent DP passes rather than derived from a single combined array?

Derived from the classic LIS decomposition technique for bitonic/mountain subsequence problems; hand-verified against the standard array example {4,2,3,6,10,1,12}, where the maximum bitonic length is 5, tied at peaks 10 (i=4) and 12 (i=6).