eTonno influencers accuracy

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<int>& prices) 
{
    auto profit = 0;
    auto lastBuy = prices[0];
    auto last = prices[0];
    for (auto i : prices)
    {
        if (i<last)
        {
            profit += (last-lastBuy);
            lastBuy = last = i;
        }
        else
        {
            last = i;
        }
    }
    return profit + (last - lastBuy);
}

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:

peak and valley approach

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<int> deltas(prices.size());
adjacent_difference(begin(prices), end(prices), begin(deltas));
vector<int> 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<int> 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.

subarray patterns