### [AMAZON] Stock purchase problem

Suppose we are given an array of n integers where each index represent stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.

Clearly there is an O(n

Clearly there is an O(n

^{2}) solution to the algorithm by trying out all possible (buyDay, sellDay) pairs and taking the best out of all of them. However, is there a better algorithm, perhaps one that runs in O(n) time?
Well i will go ahead and bookmark this site to check for upcoming updates.

ReplyDelete