AlgoViz
HomeDynamic Programming

Longest Bitonic Subsequence

Medium

LIS from the left, LIS from the right

Problem

Return the length of the longest subsequence that increases then decreases.

In simple words

Combine the longest increasing run ending at each index with the longest decreasing run starting there.

The idea

A bitonic subsequence rises to a peak then falls, so compute the longest increasing run ending at each index and the longest decreasing run starting there. The best peak maximises their sum minus one for the double-counted element.

The trick

  • Answer = max(inc[i] + dec[i] - 1).
  • Decide whether a strictly monotonic sequence counts as bitonic.
  • Two O(n²) passes, or O(n log n) with tails.
2
5
3
7
101
18
0
1
2
3
4
5

Step 1 of 8. Keep the smallest tail for each length. Binary-search each number into "tails". Values: 2, 5, 3, 7, 101, 18.

1/8
Optimal
timeO(n log n)spaceO(n)

Replace the first tail ≥ x.

1// keep the smallest possible tail for each length2const tails = [];3for (const x of nums) {4  let lo = 0, hi = tails.length;5  while (lo < hi) { const m=(lo+hi)>>1;6    if (tails[m] < x) lo = m+1; else hi = m; }7  tails[lo] = x;8}9return tails.length;

Input

array
[2, 5, 3, 7, 101, 18]

Memory

num
—

Output

LIS
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 5, 3, 2]
Output:
5
Explanation:
1,2,5,3,2 rises then falls → length 5.

Example 2

Input:
nums = [1, 11, 2, 10, 4, 5, 2, 1]
Output:
6
Explanation:
1,2,10,4,2,1 → length 6.

Example 3

Input:
nums = [12, 11, 40, 5, 3, 1]
Output:
5
Explanation:
Best bitonic run is 5.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.