Length of largest bitonic - PrismoSkills
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.
Read full article from Length of largest bitonic - PrismoSkills
