We're looking at the price of a given stock over n consecutive days, numbered i = 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 sell it, if we want to maximize the profit per share, p(j) - p(i)? (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 numbers i and j in time O(n).

Acaterer knows he will need 60, 50, 80, 40 and 50 dinner napkins on five successive evenings. he can purchase new napkins initially at 25 cents each, after which he can have dirty napkins laundered by a fast one-day laundry service (i.e., dirty napkins given at the end of the day will be ready for use the following day) at 15 cents each, or by a slow two-day service at 8 cents each or both. the caterer wants to know how many napkins he should purchase initially and how many dirty napkins should be laundered by fast and slow service on each of the days in order to minimize his total costs. formulate the caterer’s problem as a linear program as follows (you must state any assumptions you make): a. define all variables clearly. how many are there? b. write out the constraints that must be satisfied, briefly explaining each. (do not simplify.) write out the objective function to be minimized. (do not simplify.)