4. Largest Bitonic Subsequence #

Created Wednesday 01 July 2020

Largest Bitonic Subsequence You are given an array of positive integers as input. Write a code to return the length of the largest such subsequence in which the values are arranged first in strictly ascending order and then in strictly descending order.

Such a subsequence is known as bitonic subsequence. A purely increasing or purely decreasing subsequence will also be considered as a bitonic sequence with the other part empty.

Note that the elements in bitonic subsequence need not be consecutive in the given array but the order should remain same. Input Format: Line 1 : A positive Integer N, i.e., the size of array Line 2 : N space-separated integers as elements of the array Output Format: Length of Largest Bitonic subsequence Input Constraints: 1<= N <= 100000 Sample Input 1: 6 15 20 20 6 4 2 Sample Output 1: 5 Sample Output 1 Explanation: Here, longest Bitonic subsequence is {15, 20, 6, 4, 2} which has length = 5. //Sample Input 2:// 2 1 5 Sample Output 2: 2 Sample Input 3: 2 5 1 Sample Output 3: 2

• This is like the longest increasing subsequence.
• We basically maintain two values, longest increasing subsequence ending at i. Longest decreasing subsequence starting from i.
• We add the pair-values and pick the maximum.
• We need to subtract one, as the topmost point was calculated for both the increasing and the decreasing part of the bitonic subarry.