Longest Bitonic Sequence

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
117 upvotes
Asked in companies
AmazonMicrosoftWells Fargo

Problem statement

A Bitonic Sequence is a sequence of numbers that is first strictly increasing and then strictly decreasing.


A strictly ascending order sequence is also considered bitonic, with the decreasing part as empty, and same for a strictly descending order sequence.


For example, the sequences [1, 3, 5, 3, 2], [1, 2, 3, 4] are bitonic, whereas the sequences [5, 4, 1, 4, 5] and [1, 2, 2, 3] are not.


You are given an array 'arr' consisting of 'n' positive integers.


Find the length of the longest bitonic subsequence of 'arr'.


Example : 
Input: 'arr' = [1, 2, 1, 2, 1]

Output: 3

Explanation: The longest bitonic subsequence for this array will be [1, 2, 1]. Please note that [1, 2, 2, 1] is not a valid bitonic subsequence, because the consecutive 2's are neither strictly increasing, nor strictly decreasing.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer 'n' denoting the number of integers in the array.

The second line contains 'n' space-separated integers, denoting the elements of the array.


Output Format : 
The output contains an integer, denoting the length of the longest bitonic subsequence.


Note: 
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1 :
5 
1 2 1 2 1


Sample Output 1:
3


Explanation For Sample Input 1:

The longest bitonic subsequence for this array will be [1, 2, 1]. Please note that [1, 2, 2, 1] is not a valid bitonic subsequence, because the consecutive 2's are neither strictly increasing, nor strictly decreasing.


Sample Input 2 :
5
1 2 1 3 4


Sample Output 2 :
4


Explanation For Sample Input 2:

The longest bitonic sequence for this array will be [1, 2, 3, 4].


Expected time complexity :
The expected time complexity is O(n ^ 2).


Constraints:
1 <= 'n' <= 10^3
1 <= 'arr[i]' <= 10^5

Time Limit: 1sec
Hint

Can we solve this problem with the help of recursion?

Approaches (3)
Recursive Approach

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: 

  1. We will iterate through the array.
  2. For finding out the length of the longest increasing sequence ending at i :
    • We will call a recursion ‘longestIncreasingSubsequence’ 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.
  3. For finding out the length of the longest decreasing sequence beginning at ‘i’ :
    • We will call a  different recursion ‘longestDecreasingSubsequence’ 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.
  4. 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.
  5. The maximum value of the bitonic sequence encountered will be our answer.
Time Complexity

O(n * (2 ^ n)), where ‘n’ is the number of elements in ‘arr’.

As the total number of different states in the recursion tree for each recursive call while iterating, can be O(2 ^ n) the overall time complexity will be O(n * (2 ^ n)).

Space Complexity

O(n), where ‘n’ is the number of elements in ‘arr’.

As there will be at most 2 * n different states of recursion that are stored in the recursion stack at a time. Hence, the space complexity will be O(n).

Code Solution
(100% EXP penalty)
Longest Bitonic Sequence
Full screen
Console