Longest Bitonic Subsequence

In this tutorial we shall solve longest Bitonic subsequence using DP.
Before solving the question, let’s understand what does Bitonic means.
Bitonic is a sequence where the number increases at certain point and decreases from that point.
For example:
Consider the array below

Longest Bitonic Subsequence
Here if you see the highlighted numbers as shown below:
Longest Bitonic Subsequence
They are the Longest bitonic subsequence.

What is a Bitonic Point?

A point where the elements are increasing and from that point they decrease is called as bitonic point.
In our example “6” is bitonic point.
Now we shall see how to solve this problem.
We shall take help of Longest Increasing Subsequence technique to solve Longest Bitonic Subsequence. Below are the steps:
1. Take Longest Increasing subsequence from Left to Right
2. Take Longest Increasing subsequence from Right to Left.
3. Take the sum at that index of both the arrays -1. The max value will be the result.
Consider the example:
Longest Bitonic Subsequence
From the image above, we can get below result:
Longest Bitonic Subsequence
Hence the longest bitonic subsequence is 5
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *