Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Longest Bitonic Subsequence

Problem Statement

Given a number sequence, find the length of its Longest Bitonic Subsequence (LBS). A subsequence is considered bitonic if it is monotonically increasing and then monotonically decreasing.

Example 1:

Input: {4,2,3,6,10,1,12}
Output: 5
Explanation: The LBS is {2,3,6,10,1}.

Example 2:

Input: {4,2,5,9,7,6,10,3,1}
Output: 7
Explanation: The LBS is {4,5,9,7,6,3,1}.

Basic Solution

A basic brute-force solution could be to try finding the Longest Decreasing Subsequences (LDS), starting from every number in both directions

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Ray

· 4 years ago

One thing that is hit or miss in these solutions is the time & space complexity analysis. Sometimes it's there, sometimes it's not.

I realize we should be able to figure it out, but I would much appreciate a textbook time & space complexity to compare my guessed complexity to. Thanks!

Show 1 reply
Iurie Gordienco

Iurie Gordienco

· 2 years ago

For [9,8,1,7,6,5,4,3,2,1] it returnes 9 should be 8