I need some hint How Can it be done in O(N)

#1

I need some hint How Can it be done in O(N).

#2

Hello @anmolaggarwal.432 follow this approach:
We create two arrays - ‘inc’ and ‘dec’

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

How can inc[i]+dec[i]-1 is the solution just didnt understand this

#4

we are compairing the dec array from the back and the incr from start as at the particular index we have calculated and then we are compairing at that point the answer coming out to be the maximum or not.