Longest Bitonic Sequence
Last Updated: 2 Jan, 2021
Difficulty: Moderate
You are given an array/list 'ARR' consisting of 'N' positive integers. A subsequence of 'ARR' is called bitonic if it is first increasing and then decreasing.
For Example:
An example of a bitonic sequence will be 1 < 2 < 3 < 4 > 2 > 1.
Your task is to return the length of the longest bitonic sequence of 'ARR'.
A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array.
For Example:
Let ARR = [1, 2, 1, 2, 1]
One of the bitonic subsequences for this array will be [1, 2, 2, 1].
Input Format
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.
Output Format :
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.
Note:
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10^3
1 <= ARR[i] <= 10^5
Time Limit: 1sec
Approach 1
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 will iterate through the array.
- For finding out the length of the longest increasing sequence ending at i :
- We will call a recursion ‘longestIncreasing’ keeping the current index, the last element included in the subsequence as the parameter. Let that element be ‘LAST’.
- In each recursive call:
- If (‘ARR[CURRINDEX]’ > ‘LAST’) we include ‘ARR[CURRINDEX]’ in our subsequence and recur again.
- Else, we recur without including ‘ARR[CURRINDEX]’ in our subsequence.
- For finding out the length of the longest decreasing sequence beginning at ‘i’ :
- We will call a different recursion ‘longestDecreasing’ keeping the current index, the last element included in the subsequence as the parameter. Let that element be ‘LAST’.
- In each recursive call, we will:
- If (‘ARR[CURRINDEX]’ < ‘LAST’) we include ‘ARR[CURRINDEX]’ in our subsequence and recur again.
- Else, we call recur without including ‘ARR[CURRINDEX]’ in our subsequence.
- The length of the longest bitonic sequence containing index ‘i’, will be the longest increasing subsequence containing ‘i’ + longest decreasing subsequence containing index ‘i’ - 1.
- The maximum value of the bitonic sequence encountered will be our answer.
Approach 2
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 will call a recursion with the current index ‘CURRINDEX’, the last index ‘LAST’ included in our subsequence, and a boolean variable ‘CHECK’ denoting whether it is the increasing or decreasing part of the bitonic sequence as our parameters.
- In each recursive call:
- We will call the recursion without including ‘ARR[CURRINDEX]’ in our subsequence.
- If (‘CHECK’ == 0), it denotes that we are in the increasing part of the bitonic sequence, so we check if ‘ARR[CURRINDEX]’ > ‘ARR[LAST]’. If it is true we include it in our subsequence and call the recursion.
- If (‘CHECK’ == 1), it denotes that we are in the decreasing part of the bitonic sequence, so we check if ‘ARR[CURRINDEX]’ < ‘ARR[LAST]’. If it is true we include it in our subsequence and call the recursion.
Approach 3
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:
- We will declare array/list ‘LIS’ and ‘LDS’ which store the length of the longest increasing subsequence ending at index ‘i’, and the length of the longest decreasing subsequence beginning at index ‘i’, respectively.
- For computing ‘LIS[i]’ we will-
- Iterate over all ‘j’ which are less than ‘i’.
- If ‘ARR[j]’ < ‘ARR[i]’ we update ‘LIS[i]’ as max(‘LIS[i]’, ‘LIS[j]’ + 1).
- For computing ‘LDS[i]’ we will-
- Iterate over all ‘j’ which are greater than ‘i’.
- If ‘ARR[j]’ > ‘ARR[i]’ we update ‘LDS[i]’ as max(‘LDS[i]’, ‘LDS[j]’ + 1).
- Finally, we will iterate through all indices ‘i’, and compute the length of the longest bitonic sequence containing index ‘i’, as (‘LDS[i]’ + ‘LIS[i]’ - 1) and return the maximum as our answer.
