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.
Got a thought to share or found a bug in the code? We'd love to hear from you:
