Print the Longest Bitonic Subsequence
Given an array you have to print the longest bitonic subsequence from the array. A bitonic sequence is a sequence where numbers of that sequence are sorted and they are increasing first then decreasing.
Note: A sorted increasing sequence is also a bitonic sequence and similarly sorted decreasing sequence is a bitonic sequence.
Test Case T
T no. of lines with the value of N and corresponding values.
E.g.
3
5
1 4 2 5 7
8
1 7 3 2 5 4 8 1
17
1 10 9 3 5 4 11 7 4 8 9 6 19 5 7 8 2
Constrains:
1≤ T ≤ 10
1≤ N ≤ 100
1≤ A[i] ≤ 1000
Output:
Print the bitonic subsequence.
Example
T=3
N=5
1 4 2 5 7
1 2 5 7
N=8
1 7 3 2 5 4 8 1
1 7 3 2 1
N=17
1 10 9 3 5 4 11 7 4 8 9 6 19 5 7 8 2
1 3 4 7 8 9 6 5 2
For this sequence:
Longest increasing subsequence from front:
Longest increasing subsequence from rear:
After add up:
Therefore, the length of the longest bitonic subsequence is 5.
Therefore, the numbers from the first LIS are: 1 7
Therefore, the numbers from the second LIS are: 3 2 1
Therefore, the sequence will be 1 7 3 2 1
C++ implementation:
Output