See the original problem on HackerRank.
Solutions
A good strategy consists in selling one share only if that increases someday in the future. The best time to sell it corresponds to highest price reached after the day we buy the stock.
For instance:
1

2 5 100 
The best strategy is:
 at day 1 we buy the stock and we pay 2
 at day 2 we buy the stock and we pay 5 (we don’t sell the stock bought before yet)
 at day 3 we sell both the stocks by earning 1002 + 1005 = 193
In other words, the best strategy consists in buying every stock at price \(p_i\) only if in the future the stock price \(p_i\) is surpassed. In the example above, 2 and 5 are surpassed by 100. 100 itself is not surpassed though.
Algorithmically, for each price \(p_i\) at position \(i\) we need to find the maximum price \(m_i\) that is greater than \(p_i\) (if any) from \(i\) to \( N \). Then we sum to our total profit \(m_i  p_i\).
The tricky part is finding such a maximum value in an efficient way. The quadratic solution is easy: for each price \(p_i\) we just iterate forward to find the maximum price that is greater than \(p_i\). The code is left to the reader.
To find an efficient solution we can think…backwards! We iterate the prices backwards and we keep track of the maximum price so far:


This solution is linear.
Emerging patterns
Two patterns emerge from the snippet above:
 prefix sum
 zip  map  reduce
So we can rewrite the code this way:


And then:


In C++20 we can use ranges to remove both the additional storage and the extra scan:


Since Python 3.2 we can use itertools.accumulate
that makes an iterator returning accumulated “sums” (customizable):


For the curious C++ developer, here are two related posts by Marco Arena:
An alternative approach using a stack by Andrea Battistello:

