An example of a bitonic sequence will be 1 < 2 < 3 < 4 > 2 > 1.
Let ARR = [1, 2, 1, 2, 1]
One of the bitonic subsequences for this array will be [1, 2, 2, 1].
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains a single integer ‘N’ denoting the number of integers in the array/list.
The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array.
For each test case, print an integer denoting the length of the longest bitonic sequence.
Output for each test case will be printed in a new line.
You don’t need to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= N <= 10^3
1 <= ARR[i] <= 10^5
Time Limit: 1sec
The key observation here is that for each index ‘i’, of ‘ARR’ the length of the bitonic sequence containing index ‘i’, will be the sum of the length of the longest increasing subsequence ending at ‘i’, and the length of longest decreasing subsequence beginning at ‘i’. We can use a recursive approach for finding the length of the longest increasing and decreasing subsequence.
The algorithm will be:
We can use memoization to optimize the recursive approach. Since many recursive calls have to be made with the same parameters, this redundancy can be eliminated by storing the results obtained for a particular call in memoization in a matrix ‘MEMO’.
The algorithm will be:
We can use dynamic programming to find the length of the longest increasing subsequence ending at index ‘i’, and the length of the longest decreasing subsequence beginning at index ‘i’.
The algorithm will be: