Dynamic Programming21 sections · 916 units
Open in Course

Longest Bitonic Subsequence - Problem Statement

Bidirectional LIS

A bitonic sequence first increases, then decreases. Find the longest bitonic subsequence. For [1, 11, 2, 10, 4, 5, 2, 1], the answer is 6 because the longest bitonic subsequence has 6 elements, for example [1, 2, 10, 4, 2, 1] (increases to 10, then decreases).

The key: every element could be the peak. You need to know the LIS ending at each position AND the LDS (longest decreasing subsequence) starting at each position.