# eTonno influencers accuracy

See the original problem on HackerRank.

## Solutions

A brute-force solution (considering the set of all possible transactions) is clearly too expensive.

To grasp the optimal solution, consider this example:

 1  1, 7, 2, 3, 6, 7, 6, 7 

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

 1  (buy=1, sell=7) + (buy=2, sell=7) + (buy=6, sell=7) = 6 + 5 + 1 = 12 

Look at the increasing sub-series 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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  int maxProfit(const vector& prices) { auto profit = 0; auto lastBuy = prices; auto last = prices; for (auto i : prices) { if (i

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:

 1  1, 7, 2, 3, 6, 7, 6, 7 

Again, this set of transactions gives the maximum profit:

 1  (buy=1, sell=7) + (buy=2, sell=7) + (buy=6, sell=7) = 6 + 5 + 1 = 12 

However, we get the very same result even if we do the other micro-transactions in between:

 1  (buy=1, sell=7) + (buy=2, sell=3) + (buy=3, sell=6) + (buy=6, sell=7) + (buy=6, sell=7) = 6 + 1 + 3 + 1 + 1 = 12 

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:

 1 2 3 4 5 6 7  auto maxProfit = 0; for (auto i = 1u; i < prices.size(); ++i) { if (prices[i] > prices[i - 1]) maxProfit += prices[i] - prices[i - 1]; } return maxProfit; 

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:

 1 2 3 4 5 6 7  vector deltas(prices.size()); adjacent_difference(begin(prices), end(prices), begin(deltas)); vector positives; copy_if(next(begin(deltas)), end(deltas), back_inserter(positives), [](auto i){ return i > 0; }); cout << accumulate(begin(positives), end(positives), 0); 

Or:

 1 2 3 4 5  vector deltas(prices.size()); adjacent_difference(begin(prices), end(prices), begin(deltas)); cout << accumulate(next(begin(deltas)), end(deltas), 0, [](auto sum, auto i){ return i > 0 ? sum + i : sum; }); 

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

 1 2 3 4 5  auto deltas = views::zip_with(std::minus<>{}, views::drop(prices, 1), prices); auto filtered = ranges::views::filter(deltas, [](auto i){ return i > 0; }); std::cout << ranges::accumulate(filtered, 0); 

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

We've worked on this challenge in these gyms: modena