☕ DSA Java Articles

Topics › Dynamic Programming › DP on LIS

Longest Bitonic Subsequence

Medium TUF ID 633 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array nums of n integers. A subsequence keeps the original order of the elements it uses but may skip any of them. A subsequence is bitonic if it first strictly increases and then strictly decreases. Return the length of the longest bitonic subsequence.

This article follows the convention of Striver’s DP-46: a subsequence that only increases, or only decreases, also counts as bitonic, because one of its two parts may be empty. Under that rule every non-empty array has an answer of at least 1. The usual constraint is n ≤ 10^3, so an O(n^2) solution is what is expected; an O(n log n) version is shown at the end for larger inputs.

Example 1

nums = [1, 2, 5, 3, 2]
answer = 5               // the whole array: 1 2 5 rises, 5 3 2 falls

Example 2

nums = [1, 11, 2, 10, 4, 5, 2, 1]
answer = 6               // 1 2 10 4 2 1 (also 1 2 4 5 2 1, and 1 11 10 4 2 1)

Example 3

nums = [80, 60, 30, 40, 20, 10]
answer = 5               // 80 60 30 20 10, a purely decreasing subsequence

Approach 1: Brute force

Intuition. There are 2^n subsequences. We can describe each one with a bitmask, walk it once and decide whether it is bitonic. While walking we keep one flag, falling, that turns on the first time a value drops. After that, any rise breaks the shape. An equal pair breaks it in either phase, because both parts must be strict.

Algorithm.

  1. For every non-empty mask from 1 to 2^n - 1:
  2. Walk the chosen indices left to right, tracking the previous value prev and the flag falling.
    • Equal to prev: not bitonic.
    • Smaller than prev: set falling = true.
    • Larger than prev while falling: not bitonic.
  3. If the walk survives, update the best length with the number of chosen elements.
static int bruteForce(int[] nums) {
    int n = nums.length, best = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        int len = 0, prev = 0;
        boolean falling = false, ok = true;
        for (int i = 0; i < n && ok; i++) {
            if ((mask & (1 << i)) == 0) continue;
            if (len > 0) {
                if (nums[i] == prev) ok = false;                // equal neighbours are never allowed
                else if (nums[i] < prev) falling = true;        // we are past the peak
                else if (falling) ok = false;                   // a rise after the peak
            }
            prev = nums[i];
            len++;
        }
        if (ok) best = Math.max(best, len);
    }
    return best;
}

Complexity. Time O(2^n · n): every mask is walked once. Space O(1).

This is only useful as a reference to test the faster methods against; already at n = 30 it does a billion walks.

Approach 2: Better, two LIS arrays

Intuition. Every bitonic subsequence has a peak: its largest element, sitting at some index i. Everything before the peak is a strictly increasing subsequence that ends at i and uses only indices < i. Everything after the peak is a strictly decreasing subsequence that starts at i and uses only indices > i.

The crucial observation is that these two halves do not constrain each other. The left half only needs values smaller than nums[i], and so does the right half. A value on the left may even equal a value on the right (as in 1 2 1). So for a fixed peak the best we can do is simply the best left half plus the best right half, which are two independent LIS questions:

Both arrays count nums[i] itself, so the bitonic length with peak i is inc[i] + dec[i] - 1. The answer is the maximum over all i. A purely increasing subsequence is the case where the peak is its last element and dec[i] = 1; a purely decreasing one has inc[i] = 1. Both are covered automatically.

Algorithm.

  1. For each i from left to right: inc[i] = 1 + max(inc[j]) over j < i with nums[j] < nums[i] (or 1 if there is no such j).
  2. For each i from right to left: dec[i] = 1 + max(dec[j]) over j > i with nums[j] < nums[i].
  3. Return the maximum of inc[i] + dec[i] - 1.
static int better(int[] nums) {
    int n = nums.length, best = 0;
    int[] inc = new int[n], dec = new int[n];
    for (int i = 0; i < n; i++) {
        inc[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) inc[i] = Math.max(inc[i], inc[j] + 1);
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        dec[i] = 1;
        for (int j = n - 1; j > i; j--) {
            if (nums[j] < nums[i]) dec[i] = Math.max(dec[i], dec[j] + 1);
        }
    }
    for (int i = 0; i < n; i++) best = Math.max(best, inc[i] + dec[i] - 1);  // nums[i] is the peak, counted once
    return best;
}

Dry run on Example 2:

i 0 1 2 3 4 5 6 7
nums 1 11 2 10 4 5 2 1
inc 1 2 2 3 3 4 2 1
dec 1 5 2 4 3 3 2 1
inc + dec - 1 1 6 3 6 5 6 3 1

Three different peaks reach 6: 11 (1 11 10 4 2 1), 10 (1 2 10 4 2 1) and 5 (1 2 4 5 2 1).

Complexity. Time O(n^2): each of the two passes compares every pair once. Space O(n) for the two arrays.

Intuition. Approach 2 spends O(n^2) only on building inc and dec. Both can be built in O(n log n) with the “tails” technique from the binary-search LIS.

Keep an array tails where tails[k] is the smallest value that can end a strictly increasing subsequence of length k + 1 among the elements processed so far. That array is itself strictly increasing. When the next value x = nums[i] arrives, find lo, the number of tails that are smaller than x (the first position with tails[lo] >= x):

Hence the longest strictly increasing subsequence ending exactly at i has length lo + 1. Recording that number at every step gives inc. Then x replaces tails[lo], because it is a smaller (or new) ending for length lo + 1. The usual binary-search LIS only reports the final size of tails; here we keep the per-index lengths, which is exactly what the peak formula needs. Running the same routine from right to left gives dec.

Algorithm.

  1. inc = lisEndingAt(nums, false), scanning left to right.
  2. dec = lisEndingAt(nums, true), scanning right to left.
  3. Return the maximum of inc[i] + dec[i] - 1.
static int optimal(int[] nums) {
    int n = nums.length, best = 0;
    int[] inc = lisEndingAt(nums, false), dec = lisEndingAt(nums, true);
    for (int i = 0; i < n; i++) best = Math.max(best, inc[i] + dec[i] - 1);
    return best;
}

static int[] lisEndingAt(int[] nums, boolean fromRight) {
    int n = nums.length, size = 0;
    int[] tails = new int[n], len = new int[n];             // tails[k] = smallest tail of a run of length k + 1
    for (int step = 0; step < n; step++) {
        int i = fromRight ? n - 1 - step : step;
        int lo = 0, hi = size;                              // find the first tail >= nums[i]
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < nums[i]) lo = mid + 1; else hi = mid;
        }
        tails[lo] = nums[i];
        if (lo == size) size++;
        len[i] = lo + 1;                                    // lo tails are smaller than nums[i]
    }
    return len;
}

Complexity. Time O(n log n): two scans, each doing one binary search per element. Space O(n).

Edge cases and pitfalls