Introduction
Problem statement
We are given an array of size N. Our task is to find the length of the Longest Bitonic Subsequence present in the given array.
Bitonic Subsequence: A subsequence that is first increasing and then decreasing.
 An ascending order sequence is also considered bitonic, with the decreasing part as empty.
 A descending order sequence is also considered bitonic, with the increasing part as empty.
Sample Examples
Example 1:
Input: a[] = { 7, 9, 5, 10, 13, 2, 3, 6 }
Output: 5
Explanation
Longest Bitonic Subsequence: {7, 9, 10, 13, 6}
Example 2:
Input: a[]= { 10, 22, 9, 33, 21, 50, 41, 60, 80, 3 }
Output: 7
Explanation
Longest Bitonic Subsequence: { 10, 22, 33, 50, 60, 80, 3 }
Approach
This is a standard dynamic programming problem variation, the Longest increasing subsequence (LIS). A bitonic sequence is first increasing and then decreasing sequence.
We first calculate the length of all the longest increasing subsequences ending with a[i] and decreasing subsequences starting with a[i] in the given array using dynamic programming.
The length of the longest bitonic subsequence in the given array:
Length of longest increasing subsequence at index (i) + Length of the longest decreasing subsequence at index (i)  1, where i ranges from 0 to n1.
Here, we are subtracting 1 as we are adding a[i] twice in our longest increasing and decreasing subsequence.
Letâ€™s understand the above approach with an example:
Longest increasing subsequence:
Given array  10  22  9  33  21  50  41  60  80  3 
Longest length  1  2  1  3  2  4  4  5  6  1 
Increasing subsequences  10 
10 22 
9 
10 22 33 
10 21 
10 22 33 50 
10 22 33 41 
10 22 33 50 60 
10 22 33 50 60 80 
3 
Longest decreasing subsequence:
Given array  10  22  9  33  21  50  41  60  80  3 
Longest length  3  3  2  3  2  3  2  2  2  1 
Decreasing subsequences 
10 9 3 
22 9 3 
9 3 
33 21 3 
21 3 
50 41 3 
41 3 
60 3

80 3

3 
If we consider the Increasing subsequence : {10, 22, 33, 50, 60, 80} of length 6 and the Decreasing subsequence: {80, 3} of length 2.
Max length = (6 + 2)  1 = 7 // subtracting 1 because 80 is considered twice.
Longest Bitonic Subsequence obtained: { 10, 22, 33, 50, 60, 80, 3 }