Problem 4. Highway Restaurants (25 points)

(a) (18 points) You want to open a chain of restaurants along a given highway, which starts at mile marker 1 and ends at some mile marker n. Each mile marker is a possible location where you can build a restaurant, and you are given an array P[1 . . . n], where P[i] is the profit you get for building at mile marker i. You can build as many restaurants as you want (and the cost of building is already factored into P[i]), however, any two restaurants you build must be m miles apart so that they do not compete with one another. Using dynamic programming, give an O(n) time algorithm to compute the maximum possible profit you can get from building restaurants.

(b) (7 points) Describe how to modify you solution from part (a) to return a list of the mile markers where you should build your restaurants to get the maximum profit.