Maximum length biotonic problem

#1

why we are making auxillary arrays and why we are adding 1 each time when array is increasing and finally why we are finding maximum value of inc[i]+dec[i]-1.

#2

auxiliary arrays are made to store the previous answers we have already computed.
we are computing the maximum because we need to find the maximum length of the bitonic subarray
i think you have not understood the question. Go through the question once again and if you still don’t understand then you ask again here

  1. Construct an auxiliary array inc[] from left to right such that inc[i] contains length of the nondecreaing subarray ending at arr[i].
    For A[] = {12, 4, 78, 90, 45, 23}, inc[] is {1, 1, 2, 3, 1, 1}

  2. Construct another array dec[] from right to left such that dec[i] contains length of nonincreasing subarray starting at arr[i].
    For A[] = {12, 4, 78, 90, 45, 23}, dec[] is {2, 1, 1, 3, 2, 1}.

  3. Once we have the inc[] and dec[] arrays, all we need to do is find the maximum value of (inc[i] + dec[i] – 1).
    For {12, 4, 78, 90, 45, 23}, the max value of (inc[i] + dec[i] – 1) is 5 for i = 3.

2 Likes
#3

i am still unable to understand the auxilary arrays how you are calculting

#4

you can refer this https://ide.codingblocks.com/s/94146
dry run the logic then you will definately understand

#5

i dry run on the above code it is perfect but can you tell me how you get the logic of max1=max(max1,inc[i]+dec[i]-1) pls can you explain it

1 Like