unable to understand… plz explain me on call,
call me on 639481623
Max length bitonic subarray
hello @shikharskj
consider an index i .
if u know longest increasing sequence thats ends at i and longest decreasing sequence that starts from i then finding bitonnic sequence with i as pivot will be easy right?
it l1 is length of longest increasing sequence ending at i.
if l2 is length of longest decreasing sequence starting from i
then bitonnic length with pivot i will be l1 + l2 -1 (-1 becuase we have consider i in both the sequence )
now if we repeat this process for all values of i { 0 … n-1 } and pick maximum of all it will be our answer right?
how to construct increasing / decreasing array?
if u r at index i then u can add it to sequence ending at index i-1 only when a[i] > a[i-1] right ? becuase then only the sequnce will be increasing.
so in that case increasing[i]= 1+ increasing[i-1]
this is what they are doing
same logic holds for decreasing array
implementation details->
we will maintain two array lets say dec and inc .
value at ith index of inc array will tell the longest increasing subarray ending at ith index.
value at ith index of dec array will tell u longest decreasing subbarray starting from ith index.
Now after constructing these two array we can answer this problem easily
we will iterate from i=0 to i=n-1 and store maximum value of inc[i]+dec[i]-1
plz call me on 6394816023
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.