Longest Bitonic Subsequence

Medium
1611.

Longest Bitonic Subsequence

Longest Bitonic Subsequence is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

A sequence is bitonic if it first strictly increases and then strictly decreases, and both parts are non-empty — that is, it rises to a single peak and then falls, like 1, 4, 6, 3, 2. A sequence that only increases, or only decreases, is not bitonic.

Given an array nums, return the length of its longest bitonic subsequence (elements kept in their original order, not necessarily adjacent). If no bitonic subsequence exists, return 0.

Example 1

Input
nums = [1,2,5,3,2]
Output
5
Explanation
The whole array rises 1, 2, 5 and falls 5, 3, 2.

Example 2

Input
nums = [1,11,2,10,4,5,2,1]
Output
6
Explanation
One longest choice is 1, 2, 10, 4, 2, 1.

Example 3

Input
nums = [10,20,30]
Output
0
Explanation
The array only increases, so no subsequence can fall after its peak.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestBitonicSequence = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Bitonic Subsequence — Solution in Python, Java & C++

Longest Bitonic Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Bitonic Subsequence is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Problem statement

A sequence is bitonic if it first strictly increases and then strictly decreases, and both parts are non-empty — that is, it rises to a single peak and then falls, like 1, 4, 6, 3, 2. A sequence that only increases, or only decreases, is not bitonic.

Given an array nums, return the length of its longest bitonic subsequence (elements kept in their original order, not necessarily adjacent). If no bitonic subsequence exists, return 0.

Example 1

Input: nums = [1,2,5,3,2]
Output: 5
Explanation: The whole array rises 1, 2, 5 and falls 5, 3, 2.

Example 2

Input: nums = [1,11,2,10,4,5,2,1]
Output: 6
Explanation: One longest choice is 1, 2, 10, 4, 2, 1.

Example 3

Input: nums = [10,20,30]
Output: 0
Explanation: The array only increases, so no subsequence can fall after its peak.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4

Hints for Longest Bitonic Subsequence

  1. Hint 1

    Every bitonic subsequence has a peak element. To its left is a strictly increasing subsequence ending at the peak, to its right a strictly decreasing one starting at it.

  2. Hint 2

    Compute, for each index i, the longest strictly increasing subsequence ending at i (up[i]) and the longest strictly decreasing subsequence starting at i (down[i]).

  3. Hint 3

    The best bitonic subsequence with peak i has length up[i] + down[i] - 1 — but only count peaks where up[i] > 1 and down[i] > 1, so both sides are non-empty.

How to solve Longest Bitonic Subsequence

Split a bitonic subsequence at its peak. The rising half is any increasing subsequence ending at the peak and the falling half any decreasing subsequence starting there; the two halves only share the peak, so they can be optimised independently — two LIS computations, one from each side.

Approach

  1. up[i] = 1 + max up[j] over j < i with nums[j] < nums[i] (1 if none).
  2. down[i] = 1 + max down[j] over j > i with nums[j] < nums[i] (1 if none), filled from the right.
  3. Answer = max of up[i] + down[i] - 1 over all i with up[i] >= 2 and down[i] >= 2; 0 if there is no such i.

Why it works

For a fixed peak i, any increasing subsequence ending at i and any decreasing subsequence starting at i concatenate (sharing i) into a valid bitonic subsequence, because every element on the left is before i and smaller than nums[i], and every element on the right is after i and smaller too. Maximising each half separately therefore maximises the total for that peak, and the best peak gives the answer.

Complexity

  • Time — O(n^2) (O(n log n) with patience sorting for both halves)
  • Space — O(n)

Pitfalls

  • Both halves must be non-empty: a purely increasing or decreasing array answers 0, not its length.
  • Strictly: equal neighbours cannot both be in one half — use <, not <=.
  • The peak is counted in both up and down, hence the - 1.

Reference solution

Python

from typing import List

def longestBitonicSequence(nums: List[int]) -> int:
    n = len(nums)
    up = [1] * n
    down = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and up[j] + 1 > up[i]:
                up[i] = up[j] + 1
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if nums[j] < nums[i] and down[j] + 1 > down[i]:
                down[i] = down[j] + 1
    best = 0
    for i in range(n):
        if up[i] > 1 and down[i] > 1:
            best = max(best, up[i] + down[i] - 1)
    return best

Java

public static int longestBitonicSequence(int[] nums) {
    int n = nums.length;
    int[] up = new int[n], down = new int[n];
    for (int i = 0; i < n; i++) {
        up[i] = 1;
        for (int j = 0; j < i; j++) if (nums[j] < nums[i]) up[i] = Math.max(up[i], up[j] + 1);
    }
    for (int i = n - 1; i >= 0; i--) {
        down[i] = 1;
        for (int j = i + 1; j < n; j++) if (nums[j] < nums[i]) down[i] = Math.max(down[i], down[j] + 1);
    }
    int best = 0;
    for (int i = 0; i < n; i++) {
        if (up[i] > 1 && down[i] > 1) best = Math.max(best, up[i] + down[i] - 1);
    }
    return best;
}

C++

int longestBitonicSequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> up(n, 1), down(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i]) up[i] = max(up[i], up[j] + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            if (nums[j] < nums[i]) down[i] = max(down[i], down[j] + 1);
    int best = 0;
    for (int i = 0; i < n; i++)
        if (up[i] > 1 && down[i] > 1) best = max(best, up[i] + down[i] - 1);
    return best;
}

JavaScript

var longestBitonicSequence = function(nums) {
    var n = nums.length;
    var up = new Array(n).fill(1), down = new Array(n).fill(1);
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < i; j++) if (nums[j] < nums[i] && up[j] + 1 > up[i]) up[i] = up[j] + 1;
    }
    for (var a = n - 1; a >= 0; a--) {
        for (var b = a + 1; b < n; b++) if (nums[b] < nums[a] && down[b] + 1 > down[a]) down[a] = down[b] + 1;
    }
    var best = 0;
    for (var k = 0; k < n; k++) {
        if (up[k] > 1 && down[k] > 1 && up[k] + down[k] - 1 > best) best = up[k] + down[k] - 1;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming