Harsh Gupta
Jun 15th, 2010, 12:23 AM
Hi,
This is an Algorithm question. I found this sample question and have troubles solving it. I am pasting the question here as it is, so as to avoid any confusion:
Consider the following scenario, you are given all the daily closing prices of shares of a company XYZ over a period of n days. You are given a chance to buy 100 shares of this stock at any day i, 1 <= i <= n and sell at any day j, i <= j <= n. Of course your objective is to maximize your profit in this transaction. There is a simplistic O(n2) algorithm that tries all possible pairs of buy/sell days to find the optimal solution. Develop an algorithm that accomplishes this in O(n) time.
Any takes?
Thank you
This is an Algorithm question. I found this sample question and have troubles solving it. I am pasting the question here as it is, so as to avoid any confusion:
Consider the following scenario, you are given all the daily closing prices of shares of a company XYZ over a period of n days. You are given a chance to buy 100 shares of this stock at any day i, 1 <= i <= n and sell at any day j, i <= j <= n. Of course your objective is to maximize your profit in this transaction. There is a simplistic O(n2) algorithm that tries all possible pairs of buy/sell days to find the optimal solution. Develop an algorithm that accomplishes this in O(n) time.
Any takes?
Thank you