There are n cities in a circle and distance between every adjacent pair of cities was given. We were asked to determine a pair of cities such that the minimum distance to travel between them is maximum.
For example,the input may be: 8 12 16 10 3 13.
We can definitely solve this in O(n2) complexity.Can we improve the complexity any further?how?
If I'm not wrong, you need to search for a consecutive segment in the circular array such that the difference of this segment and the remaining segment is as low as possible. You can do that by concatenating the array with itself, and then calculating prefix sums. Then for each possible starting index do 2 binary searches. 1st for maximum segment sum ≤ half the total sum. And, the 2nd one similar for minimum segment sum ≥ half the total sum. 2 pointer approach should also work.