Yuckdonald's is considering opening a series of restaurants along Quaint Valley Highway (QVH).Give an efficient algorithm to compute the maximum expected total profit subject to the given constraints.

A Reader send me this interestinmg problem some times back & he also confirmed that recently google asked it :)

Yuckdonald's is considering opening a series of restaurants along Quaint Valley Highway (QVH).The n possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order,m1;m2; : : : ;mn.

The constraints are as follows:

1)At each location,Yuckdonald's may open at most one restaurant. The expected profi t from opening a restaurant at location i is pi, where
pi > 0 and i = 1; 2; : : : ; n.

2)Any two restaurants should be at least k miles apart, where k is a
positive integer.

Give an efficient algorithm to compute the maximum expected total
profit subject to the given constraints.

More Info About The Problem can be found here
http://www.cs.grinnell.edu/~coahranm/csc301/f2007/hw/a8.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf
https://groups.google.com/forum/#!topic/algogeeks/JUpjPTR494Y
http://www.solvemyproblem.net/Webed/forum/thread.asp?tid=1213