1 Suppose we drive a pickup truck from city A to city B. Along the high way, we
ID: 3624075 • Letter: 1
Question
1 Suppose we drive a pickup truck from city A to city B. Along the high way, we will go through n apple markets, labeled with 1, 2, …, n, where you can buy or sell apples. City A and city B also have an apple market each. For convenience, we label city A with 0 and city B with n+1. From a customer point of view, the buying price B[i] and selling price S[i] (dollar per pound) at market i are known. An example with n = 4 is given below.
values at
city A market1 market2 market3 market4 City B
b[0]=5 b[1]=4 b[2]=8 b[3]=2 b[4]=7 b[5]=9
s[0]=3 s[1]=3 s[2]=7 s[3]=1 s[4]=6 s[5]=7
Now, we will stop at one of the stations to buy apples and then stop at another station to sell apples. Please design an O(n) greedy algorithm to find market i to buy apples, and find market j greater than or equal i to sell apples such that the profit will be maximized. We assume that it would be too costly and forbidden to drive backward. In the above example, the best result is to buy apples at market 3 and sell them at market 5 with profit of (7-2 = 5) dollars per pound. It is allowed that i = j which means you buy and sell apples at the same market i.
2 Design a divide and conquer algorithm to solve problem 2. The time complexity of your algorithm must be O(nlgn) or better.
Explanation / Answer
The idea behind this is simple. Find the highest value in the S array (as long as it is not S[0]).
If it is S[0] then find the next highest element.
Once you have the most logical sell point, keep track of the index. Then find the lowest buy value as long as it is in the index range of 0 through index - 1.
This should give you the "best" buy and sell point.
Generally what I said above is correct, but obviously you're problem isn't that simple. You can adjust it to be correct for your situation by making a couple small modifications. Namely, after you find the highest sell price, and the lowest buy price that comes before it you will also need to check the future differences after it.
After your highest sell point it may be possible that you have another sell point slightly lower, but this opens up more buy options (because it comes later), where the buy prices are much much lower. This would mean you have a lower sell price, but it would actually be much more profitable. You should be able to add this to what I mentioned before.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.