All distance minimum difference
Posted: Sat May 07, 2005 3:25 pm
My friend recently had an algorithms final exam. I got him all prepped up for dynammic programming, covering the classic examples, and then quite a few dp problems I've seen here, but the teacher gave him this problem as a dynammic programming problem, and I don't even know how to solve it.
You are given n reals (a_1, a_2, .. a_n) in sorted order, and for each k in the range 1 <= k < n, you want to find the minimum difference between a_i to a_{i+k}.
Eg, for k = 1, it is the closest two items. For k = n-1, it is the difference between the first and last items.
The bruteforce O(n^2) algorithm is easy to see, but I can't figure out anything faster.
You are given n reals (a_1, a_2, .. a_n) in sorted order, and for each k in the range 1 <= k < n, you want to find the minimum difference between a_i to a_{i+k}.
Eg, for k = 1, it is the closest two items. For k = n-1, it is the difference between the first and last items.
The bruteforce O(n^2) algorithm is easy to see, but I can't figure out anything faster.