Algorithm Design, Jon Kleinberg, Eva Tardos, Chapter 6, Exercise 7

7. As a solved exercise in Chapter 5, we gave an algorithm with O(n log n) running time for the following problem. We're looking at the price of a given stock over n consecutive days, numbered 1, 2, , n. For each day i, we have a price p(i) per share for the stock on that day. (We'll assume for simplicity that the price was fixed during each day.) We'd like to know: How should we choose a day i on which to buy the stock and a later day j>i on which to sel it, if we want to maximize the profit per Exercises 319 share, p) - p)? (If there is no way to make money during the n days, we should conclude this instead.) In the solved exercise, we showed how to find the optimal pair of days i and j in time O(n log n. But, in fact, it's possible to do better than this. Show how to find the optimal numbersi and j in time O(n