Maximizing the total viewership of the posters using Dynamic Programming

Question

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north to south). If you place a poster at position xi in the corridor, then vi>0 people will see that poster. (Some locations are more popular than others.) However, to be fair to other groups on campus, any two posters that you place must be separated by at least D feet. In other words, if you decide to place a poster at xi, then you cannot place a poster on any other bulletin board that is within D feet of xi. Given ((x1,v1), . . . ,(xn,vn),D), describe a linear-time algorithm which computes a legal postering campaign which achieves the maximum total viewership. Analyze therunning time of your algorithm