See the original problem on HackerRank.
Solutions
A bruteforce solution (considering the set of all possible transactions) is clearly too expensive.
To grasp the optimal solution, consider this example:


To obtain the maximum profit, the  possibly  most intuitive set of transactions is:


Look at the increasing subseries 2, 3, 6, 7
. Intuitively, we buy when the price starts increasing (2
) and sell when it reaches the maximum peak (7
).
Here is a way of putting together this idea:


lastBuy
memorizes the last price we bought the share, whereas last
keeps on updating as long as the price is increasing. As soon as the price gets down, we commit the transaction. In other words, this approach crunches peaks and valleys.
Working with patterns
Let’s consider again this example:


Again, this set of transactions gives the maximum profit:


However, we get the very same result even if we do the other microtransactions in between:


To visualize the solution, look at the picture here below:
Basically, the difference \(D\) corresponds exactly to the sum of the intermediate differences \(A + B + C\)!
In other words, we can sum all the positive differences along the way:


At this point, a few patterns might be recognized sharply: we accumulate the positive adjacent differences of the input array.
Here is the solution based on such patterns:


Or:


C++ ranges make the solution even clearer and more efficient (we do not allocate extra memory anymore):


Note that C++20 doesn’t provide zip_with
, instead zip_transform
will be available in C++23.