Longest Bitonic Subsequence

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftAdobe

Given an array of integers, find the length of its longest bitonic subsequence — a run of elements, not necessarily touching in the original array, that strictly climbs for a while and then strictly falls, sharing exactly one peak between the two halves. A subsequence that only climbs, or only falls, still counts as bitonic, since the missing half can simply be empty. Every element is a candidate for that shared peak. Once an index is fixed as the peak, the problem splits cleanly into two independent, already-familiar pieces: how long an increasing run can end there, coming in from the left, and how long a decreasing run can start there, going out to the right. Both of those are exactly the Longest Increasing Subsequence question — one running forward, one running backward — and adding their two lengths together, minus one for the peak counted in both halves, gives the bitonic length through that particular peak. Checking every possible peak and keeping the best result found answers the whole question.

Test Case 1:

Input:nums = [1, 9, 2, 8, 3, 7, 2, 1]

Output:6

Explanation:1, 9 climbs to a peak at 9, then 8, 3, 2, 1 comes back down — 1, 9, 8, 3, 2, 1 rises then falls for a total length of 6.

Test Case 2:

Input:nums = [1, 2, 3, 4, 5]

Output:5

Explanation:A purely increasing sequence is still bitonic — it just has an empty decreasing half. The whole array qualifies, length 5.

Test Case 3:

Input:nums = [3, 3, 3]

Output:1

Explanation:Every element is equal, so no strict rise or strict fall is possible between any pair — the best is a single element by itself.

Constraints

◆1 ≤ nums.length ≤ 12
◆-1000 ≤ nums[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

A bitonic sequence is an increasing run followed by a decreasing run that share exactly one peak element. So for every index, treating it as that peak and separately asking two questions — how long is the longest strictly increasing run that can end exactly here, and how long is the longest strictly decreasing run that can start exactly here — is enough: adding those two lengths together double-counts the peak itself, so subtracting 1 gives the bitonic length through that peak. Both of those sub-questions are solved the same way the plain Longest Increasing Subsequence recursion solves it — skip an unhelpful element or extend through it — just run once forward and once backward, with nothing cached between calls.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public int longestBitonicSubsequence(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        int best = 0;
        for (int i = 0; i < n; i++) {
            best = Math.max(best, incEndingAt(i) + decStartingAt(i) - 1);
        }
        return best;
    }

    private int incEndingAt(int i) {
        int best = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                best = Math.max(best, 1 + incEndingAt(j));
            }
        }
        return best;
    }

    private int decStartingAt(int i) {
        int best = 1;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[i]) {
                best = Math.max(best, 1 + decStartingAt(j));
            }
        }
        return best;
    }
}

Optimal — Two-Pass 1D DP

Optimal

Compute the same two quantities as arrays instead of recursive calls. inc[i] is filled by a forward pass exactly like the plain LIS table: for each index, check every earlier index and extend whichever gives the longest increasing run ending here. dec[i] is filled by a mirror-image backward pass: for each index, check every later index and extend whichever gives the longest decreasing run starting here. With both tables complete, sweeping once more and taking inc[i] + dec[i] - 1 at every index — subtracting 1 so the shared peak isn't counted twice — and keeping the largest value found gives the answer.

TimeO(n²)