Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$.
I would like to design an algorithm to find the maximum profit that you can given this array of prices. Profit is made by buying at a given date $i$ and selling at a later date $j$ so that $i \leq j$.
One easy solution is the following "exhaustive algorithm":
profit = 0 for i = 1 to N-1 for j = i+1 to N if P(j) - P(i) > profit profit = P(j) - P(i)
The issue with this however is that it takes time $\Omega(N^2)$.
Can anyone think of something faster?