Assume you are a merchant. Your aim is to maximize your profit by buying some goods preferably ata low price and then selling them preferably at a higher price afterwards. Assuming that you know themarket prices for a given period of time, your goal is to decide when to buy and when to sell in order tomaximize your profit. Do not forget that you cannot sell before you buy.

(a)15 pts.Design a divide-and-conquer algorithm to solve this problem.

(b)5 pts.Design an algorithm that is not based on the divide-and-conquer approach to solve thisproblem in linear time.

(c)5 pts.Compare these two algorithms in terms of their worst-case time complexity.

Example:Input: [10, 11, 10, 9, 8, 7, 9, 11](It means that the market price is 10on0, 11on1, ..., 11on7)Output: Buy on5for 7and sell on11for 11

.Example:Input: [100, 110, 80, 90, 110, 70, 80, 80, 90](It means that the market price is 100on0, 110on1, ..., 90on8)Output: Buy on2for 80and sell on4for 110.

Implement your solution in Python3.