Longest Bitonic Subsequence
Application of Longest Increasing Subsequence

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
Given an array arr[0 … n1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence. A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.Solution:
Longest Increasing Subsequence is an absolute prerequisite for this chapter. The first part (where the value of the items increases) of the Bitonic Subsequence is nothing but similar to finding Longest Increasing Subsequence .
Similarly, the second part, where the value of the items decreases, is similar to finding Longest Decreasing Subsequence. Longest Decreasing Subsequence is similar to Longest Increasing Subsequence, but instead of the values of the items increasing, in case of Longest Decreasing Subsequence the value of the items decreases from left to right.
O(n) Time and O(n) Space Algorithm:
Let nums[] be the given integer array.
 Create longestIncreasingSubsequence[] array based off of nums[i] from left to right where longestIncreasingSubsequence[i] gives length of longest increasing subsequence ending with nums[i], including.
 Create longestDecreasingSubsequence[] array based off of nums[i] from right to left where longestDecreasingSubsequence[i] gives length of longest decreasing subsequence starting with nums[i].
 For all i from 0 to (n  1), where n = length of nums[] array, return max(longestIncreasingSubsequence[i] + longestDecreasingSubsequence[i]  1);
Please see the inline comments in the code below for more clarification.
Code:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Other related chapters:
 Core Concept
 Box Stacking
 Russian Doll Envelopes
 Largest Divisible Subset
 Longest String Chain
 Best Team with No Conflict
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn