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!
Iurie Gordienco

Iurie Gordienco

· 2 years ago

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

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

Reading Progress

0%

Vote for new content