Notice that the series of ringing phones will always be a consecutive series from the one on the first table to the one at the ~p^\text{th}~ (prefix). Now we want to increase the prefix by adding a new phone. We can place the new phone on the table ~p+1, p+2, \dots, p+d~, because if we put it to the right of table ~p+d~, it will not ring. Obviously, it pays off the most to place the phone on table ~p+d~, because this way the new prefix will be of maximal length. We implement this by iterating from left to right and keeping track of the location of the last ringing phone, and placing the new phone if the difference between the current position and the table with the last phone is equal to ~d~. The complexity is ~\mathcal O(N)~.