Maximizing your profit

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]