Doubt in problem

#1

Hello, how to start code for this problem ? What will be it’s approach ?

#2

Hey @yashsharma4304
We create two arrays - ‘inc’ and ‘dec’

  • inc[i] stores the length of increasing subarray till i.
  • dec[i] stores the length of decreasing subarray starting from index i.
  • Doing so gives us the length of increasing and decreasing subarray at each index in O(n) time.
  • We calculate the length of the longest bitonic subarray by finding the maximum inc[i] + dec[i] - 1
  • We subtract one since the current element at ith index is included in both the increasing and decreasing subarray lengths.

Algorithm

  • Initialize inc[0] to 1 and dec[n-1] to 1
  • Creating inc[] array
    a. Till end of the array ie, i=1 to n, if arr[i] > arr[i-1] then inc[i] = inc[i-1] + 1. else, inc[i] = 1
  • Creating dec[] array
    a. From the end of the array ie, i = n-2 till i =0, if arr[i] > arr[i+1] then dec[i] = dec[i+1] +1 else, dec[i] = 1
#3

why we are doing minus 1 from inc[i] + dec[i]

#4

Ok Now I understand.

#5

Because arr[i] is considered in both inc and dec

1 Like