Make delicious recipes!

Find largest bitonic (first increasing, then decreasing) sub-array


Example: If given array is {2, 5 10, 8, 12, 15, 7, 3, 0}
The in the above array, there are two bitonics - {2,5,10, 8} and {8, 12, 15, 7, 3, 0}

Problem is to find the largest such bitonic.


Solution: We need to find an index in the array when two types of sub-arrays meet - increasing towards right and decreasing towards left.
If we can know the length of the two sub-arrays then array with the maximum length is our solution.

Construct 2 auxiliary arrays - inc and decr.
Every inc[i] stores the length of increasing sub-array ending at arr[i]

Every decr[i] stores the length of decreasing sub-array starting at arr[i]


Then the maximum bitonic length is max among inc[i]+decr[i]-1

Note that the decr array can be built by using the incr algorithm only but starting from the end of array instead of the beginning.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal