Maximum length biotonic subarray

#1

can you give a hint as to how to approach this problem? I keep getting confused in this.

#2

Hey @mansi_sharma9kF
Bitonic subarray refers to a subarray which value of elements initially increases and then decreases as we move through the subarray.
You might be knowing how to calculate maximum length increasing subsequence(MLIS) and maximum length decreasing subsequence(MLDS) using dp. So our approach to solve this question will use MLIS and MLDS.
So if you find MLIS and MLDS at each index, the length of bitonic subsequence at the index will be:
length of MLIS+lengthof MLDS-1
(because both have one common element, i.e. the element present at that index)
and the maximum of length of bitonic subsequence at all index gives you the answer.

Maximum length Biotonic Subarray
#3

Well is there any other approach to this problem since I don’t know the concepts of dp till now. How can I approach this problem in any other way than dp?

#4

Hi @mansi_sharma9kF
You can perform bottom up dp which is just like using for loops for calculating dp array.

Algorithm

  1. Initialize I[0] to 1 and D[n-1] to 1

  2. Creating I[] array
    a. Till end of the array ie, i=1 to n, if arr[i] > arr[i-1] then I[i] = I[i-1] + 1. else, I[i] = 1

  3. Creating D[] array
    a. From the end of the array ie, i = n-2 till i =0, if arr[i] > arr[i+1] then D[i] = D[i +1] +1 else, D[i] = 1

  4. Then calculate maximum by iterating i from 0 to n-1 where maximum is max(maximum,D[i]+I[i]+1);