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.
All distance minimum difference
Moderator: Board moderators
-
SilentStrike
- New poster
- Posts: 22
- Joined: Fri Jan 04, 2002 2:00 am
-
Zyaad Jaunnoo
- Experienced poster
- Posts: 122
- Joined: Tue Apr 16, 2002 10:07 am