Maximizing your profit [Solution]

Problem was here: http://ruffnsluff.blogspot.com/2016/08/maximizing-your-profit.html


To repeat:
Suppose you had $K$ dollars and knew the price of gold over the next $n$ days. You want to invest all the $K$ dollars in buying gold once, and then sell all the gold at a later day (both among those $n$ days).

You want to maximize your profit.

Assume you get the prices as an array of length $n$.

Can you find an $O(n)$ time algorithm for this?

Solution

---

If you invest $K$ dollar at price $p_i$, you get $\dfrac{K}{p_i}$ units of gold. If you now sell at $p_j$, the profit you make of $\dfrac{K \times p_j}{p_i}- K$.

Thus you just need to maximize $\dfrac{p_j}{p_i}$.

This you can do by keeping track of the min $p_i$ seen so far, and the max possible $\dfrac{p_j}{p_i}$ as you increase $i$ (go from earlier days to later days). You can also avoid floating point compares if needed.