Suppose you follow a certain stock in the stock exchange and record the daily values of the stock you follow for a certain period (Let's assume that the values recorded for each day represent the actual price of the stock on that day). After the period is over, you want to make a simulation using the recorded values and determine the correct buying and selling days in order to take the most profitable position for that stock during this period. Naturally, in order to take the most profitable position, the purchase and sale days of the stock should be determined in such a way that the prices at the time of sale and purchase should be at the highest value compared to other alternatives, that is, we want to maximize the price difference between the two points. As an example, suppose a 4-day series is taken and the recorded price series is as follows: Day 1: $ 9 Day 2: $ 1 Day 3: $ 5 4th day: $ 4 In this case, if the purchase day is the 2nd day and the selling day is the 3rd, this operation will have a profit of $4 . Also, it is not possible to achieve a higher profit realization with any other buy / sell move. Therefore, with n = 4 and the price series given above, the solution to the problem will be a $ 4 profit value. For the problem described above, design the algorithm that finds the highest possible profit value and works with im (nlogn) asymptotic complexity and write it in pseudocode. Explain why your algorithm is linear in complexity. Hint: You should use the divide and conquer technique.
Suppose you follow a certain stock in the stock exchange and record the daily values of the stock you follow for a certain period (Let's assume that the values recorded for each day represent the actual price of the stock on that day). After the period is over, you want to make a simulation using the recorded values and determine the correct buying and selling days in order to take the most profitable position for that stock during this period. Naturally, in order to take the most profitable position, the purchase and sale days of the stock should be determined in such a way that the prices at the time of sale and purchase should be at the highest value compared to other alternatives, that is, we want to maximize the price difference between the two points.
As an example, suppose a 4-day series is taken and the recorded price series is as follows:
Day 1: $ 9
Day 2: $ 1
Day 3: $ 5
4th day: $ 4
In this case, if the purchase day is the 2nd day and the selling day is the 3rd, this operation will have a profit of $4 . Also, it is not possible to achieve a higher profit realization with any other buy / sell move. Therefore, with n = 4 and the price series given above, the solution to the problem will be a $ 4 profit value.
For the problem described above, design the
Step by step
Solved in 4 steps
