Dynamic Programming • LIS Variant

Longest Bitonic Subsequence

Find the longest subsequence that first increases, then decreases.

Overview

A bitonic subsequence goes strictly up and then strictly down. We can find this by combining two Longest Increasing Subsequences (LIS).

Compute `lis[i]`: the length of the longest increasing subsequence ending at index i.

Compute `lds[i]`: the length of the longest decreasing subsequence starting at index i (which is an LIS from right to left).

For any element at index `i`, it can be the "peak" of a bitonic subsequence. The max length with `i` as the peak is `lis[i] + lds[i] - 1`.

nums:

1

11

2

10

4

5

2

1

lis:

1

lds:

1

Code Tracker

:::

1let lis = Array(N).fill(1), lds = Array(N).fill(1);

2for (let i = 0; i < N; i++)

3 for (let j = 0; j < i; j++)

4 if (nums[i] > nums[j]) lis[i] = Math.max(lis[i], lis[j] + 1);

5for (let i = N - 1; i >= 0; i--)

6 for (let j = N - 1; j > i; j--)

7 if (nums[i] > nums[j]) lds[i] = Math.max(lds[i], lds[j] + 1);

8let maxLen = 0;

9for (let i = 0; i < N; i++)

10 maxLen = Math.max(maxLen, lis[i] + lds[i] - 1);

11return maxLen;