In this solution how will you prove that this approach will always lead to maximum possible moves ?
Intuitive explanation:
As stated from the problem, the cows will eventually occupy the consecutive position . For a given endpoint, we should move the cow to a position between the other two cows in order to ensure that the cow doesn’t occupy any endpoint again, as stated in the question. At a given point of time there are 2 endpoint and we have to make either of them inside the gap of the other and we should note that after this step, one of the gaps between cows will disappear. Here, “gap” refers to the space between an endpoint and the cow in the middle. Now, how to maximize this step? take the larger gap ofc. After that to maximize the steps we need to move the cows in such a way that each position in between them is utilized. We can do that as shown below.
For example, for 4, 9, 12 , the larger gap is b/w 4 and 9. Moving cow from 12 to 5 will make the arrangement:
4, 5, 9
then moving cow at 4 to 8, will make the arrangement:
5, 8, 9
then moving cow at 9 to 6, will make the arrangement:
5, 6, 8
then moving cow at 5 to 7, will make the arrangement:
6, 7, 8
which gives as our Ans as 4.
so the maximum steps is equal to the largest gap (9 - 4 - 1).
max_steps = max(first_half, second_half)
You can make your own test cases and convince yourself this is true. I hope I could help you in some way.