See the original problem on HackerRank.
Solutions
This problem is an application of Find the Maximum Difference.
Basically, we need to find out the maximum difference between two numbers in the given array \(max(prices[j]  prices[i])\) with \(i<j\).
The bruce force approach is quadratic and does not pass all test cases: for each element we linearly find the biggest next value.
As discussed in Find the Maximum Difference, the general solution schema is the following:


As long as we iterate the array, currMin
keeps track of the smallest element along the way. Every time we update also the global maximum difference by comparing it with the current difference.
Emerging Patterns
The code above can be decomposed into the following steps:
 calculate the array of minimum prices from \(0\) to \(N1\)
 subtract the array of prices from the array of minimum prices
 find the maximum value of that difference array
For example:




Here is a possible implementation in C++:


transform  reduce
(max_element
is an application of reduce) boils down to inner_product
(or C++17 transform_reduce
):


C++20 ranges make everything clearer and more efficient (no extra space and only one pass):


It’s interesting to note that the “dual” solution is valid as well. For example:

