I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:In a given motorcycle training circuit, the number of riders is becoming increasingly large. As such, a new set of stricter rules is being enforced.Lap times last exactly a minute, and they are booked for the full minute.If we use a free lap time slot, we must wait x seconds until we can use another.We are given a list {s1,s2,s3,...,sn} of the free slots starting time and we want to practice at least m minutes, at minimum. Find the maximum x that allows this.Example:With the list {00:00:00,00:10:03,00:14:00} and an m = 2 we can impose a maximum wait time of 00:14:00 - 00:01:00 = 00:13:00 = 1560s because we only need to lap two times, and we can do so with the first and last slot.So I tried hard and came up with this recurrence:$$X[i,m] = \max_{1 \leq j \leq i}\ (\min\ (X[j,m-1],\sum_{k=j}^{n-1}abs(s_{k+1} - s_k)))$$Where X[i,m] means the maximum distance that I can pick in the subset $\{s_1,s_2,...,s_i\}$ so that I lap at least m times.Then it's only a matter of applying dynamic programming. However, I'm not convinced that this solution is correct, because no matter how hard I try to make an algorithm out of it (using a matrix $X_{im}$) I can't come up with a good solution looking at the right bottom corner value (where i = n and m = laps requested). Any ideas or hints?Thank you.
Maximum waiting time between events such that k events are not missed
algorithms;dynamic programming;efficiency
The solution was using a binary search on the time between laps and since every checking of the value is linear time, computing the solution is cheap. Thank you anyway.