Maximum Drawdown in next-gen C++

My previous post has been well received by the ecosystem so I have decided to write a short follow-up article on another classical problem that can be solved with similar patterns.

In finance, the drawdown is the measure of the decline from a historical peak in some series of data (e.g. price of a stock on a certain period of time).

For example, here is the hypothetical price series of the fake “CPlusPlus” stock:

You know, the 2008 crisis affected C++ too, renaissance in 2011/2012, some disappointments in 2014/2015 because C++14 was a minor release and “Concepts” didn’t make it, and nowadays the stock is increasing since programmers feel hopeful about C++20.

Drawdowns are the differences between the value at one year and the value at the previous maximum peak. For instance, in 2008 we have a drawdown of 28-12 (16) and in 2015 the “dd” is 35-21 (14):

The Maximum drawdown is just the highest value among all the drawdowns. In the series above, the maximum drawdown is 16.

In economics, MDD is an indicator of risk and so an important problem to solve.

Let’s see how to solve this problem and how to bring more value out of it.

The maximum difference

The MDD problem can be formulated as follows: given an array A, find the maximum difference A[j] - A[i] with j < i. The constraint on i and j makes this problem challenging. Without it we can just find the maximum and minimum elements of the array.

The bruce force approach is quadratic in time: for each pair of indexes i, j we keep track of the maximum difference. The code follows:

int MaxDrawdownQuadratic(const vector<int>& stock)
{
    auto mdd = 0;
    for (auto j=0u; j<stock.size(); ++j)
    {
        for (auto i=j; i<stock.size(); ++i)
        {
            mdd = std::max(mdd, stock[j] - stock[i]);
        }
    }        
    return mdd;
}

When I facilitate Coding Gym, I suggest the attendees who are stuck to start from the naive solution, if any. The naive solution might be a red herring but it can lead to the optimal solution when we ask and answer key questions.

In this case the key question is “how can we remove/optimize the inner loop?”.

The current solution starts from stock[j] and it goes forward to calculate the differences between that value and all the following ones. This approach considers stock[j] like a peak and goes forward.

The key question turns to “how to avoid going through all the following elements”?

Think about the difference stock[j] - stock[i]. For every i, such a difference is maximized when stock[j] is the maximum value so far (for each j from 0 to i - 1). Thus, we can ignore all the other values since stock[j] - stock[i] would be lower.

The insight comes when we “reverse” our way of thinking about the pairs: we shouldn’t start from stock[j] and then go forward to find the lowest value. Instead, we should start from stock[i] having the previous biggest value cached!

So, instead of looking at each pair, we can just keep track of the maximum value preceding any other index. Here is the idea:

int MaxDrawdown(const vector<int>& stock)
{
    auto mdd = 0;
    auto maxSoFar = stock.front();
    for (auto i=1u; i<stock.size(); ++i)
    {
        mdd = std::max(mdd, maxSoFar - stock[i]);
        maxSoFar = std::max(maxSoFar, stock[i]);
    }
    return mdd;
}

The solution is linear in time.

Now it’s time for me to show you how to get more out of this problem. It’s time for me to inspire you to achieve more every time you face with puzzles. There is no limitation.

In the rest of the post, I’m just freely playing with the problem to express myself.

Emerging patterns

As I elaborated in the previous post, sometimes we can combine known patterns to solve problems.

I don’t have a special recipe that brings out patterns from code. Sometimes I just “see” them between the lines (as for Kadane). Other times I try some tricks to discover them. Or I don’t find any patterns at all.

I recently met again the MDD problem (after some years) and it looked to me similar to Kadane. I was biased by Kadane and my mind was unconsciously suggesting me to apply similar patterns to the MDD problem because the code looked similar. It might be dangerous! It doesn’t work every time. Ever heard about “the hammer syndrome”? This is the caveat of “thinking inside the box”. Anyway, in this case my sixth sense was right.

First of all I had an intuition: I realized that all the evolving values of maxSoFar  are totally independent from any other decision points of the algorithm. I could enumerate them separately. One trick to use when searching for patterns is asking the question “which computations can be isolated or extracted?”.

maxSoFar is just a cumulative maximum. For instance:

4 3 2 6 8 5 7 20

The cumulative maximum is:

4 4 4 6 8 8 8 20

The pattern that can generate such a series is prefix sum (when “sum” is not addition but maximum).

So I refactored the original code by isolating the cumulative maximum calculation into a separate vector:

int MaxDrawdown(const vector<int>& stock)
{
    std::vector<int> maxs(stock.size());
    std::partial_sum(std::begin(stock), std::end(stock), std::begin(maxs), [](auto l, auto r) { return std::max(l, r); });
    auto mdd = 0;
    for (auto i=1u; i<stock.size(); ++i)
    {
        mdd = std::max(mdd, maxs[i] - stock[i]);       
    }
    return mdd;
}

The next trick is to figure out if the loop hides another pattern. The question is: what kind of operation is underneath the calculation of mdd?

We have some hints:

• at every step we calculate maxs[i] - stock[i] so we read the ith-value from two sequences,
• every result of such a calculation is then reduced by applying std::max

Do you know this pattern?

Sure! It’s zip | map | reduce!

See this post for more details.

In other words:

• zip maxs with stock (we pair them off)
• map every pair with subtraction
• reduce the intermediate results of map with std::max

In C++ we can express such a pattern with std::inner_product (I’m not saying “use this in production”, I’m just letting by brain work):

int MaxDrawdown(const vector<int>& stock)
{
    std::vector<int> maxs(stock.size());
    std::partial_sum(std::begin(stock), std::end(stock), std::begin(maxs), [](auto l, auto r) { return std::max(l, r); });
    return std::inner_product(std::begin(maxs), std::end(maxs), 
                              std::begin(stock), 
                              0, 
                              [](auto l, auto r) { return std::max(l, r); }, 
                              std::minus<>{});
}

Now we have a solution that is harder for people not familiar with STL algorithms, an additional scan as well as more memory usage…

Beauty is free

First of all, although the code is not intended for production use, I am already satisfied because my brain has worked out. As you see, the line between production code and “training code” might be more or less marked. In my opinion, our brain can benefit from both training and production “styles” (when they differ).

Now, I would like to push myself even more by giving my own answer to the following question:

What might this code look like in next-generation C++?

What about using ranges? Might that help solve the issues introduced before?

Here is my answer:

int MaxDrawdown(const vector<int>& stock)
{
    auto maxs = view::partial_sum(stock, [](auto l, auto r){ return std::max(l, r); });
    auto dds = view::zip_with(std::minus<>{}, maxs, stock);
    return ranges::max(dds);
}

The combination of view::zip_with and ranges::max has displaced std::inner_product. In my opinion, it’s much more expressive.

I hope someone will propose and defend some function objects for min and max so we can avoid the lambda – after all, we have std::minus and std::plus, why not having std::maximum and std::minimum (or such)?

If you are wondering if this code does only one scan, the answer is yes. Every view here is lazy and does not use extra memory.

We can happily argue again that “beauty is free”.

Note:

usually the MDD is calculated as a ratio because it makes more sense to display it as a percentage. For example:

float MaxDrawdown(const vector<int>& stock)
{
    auto maxs = view::partial_sum(stock, [](auto l, auto r){ return std::max(l, r); });
    auto dds = view::zip_with([](auto peak, auto ith) { return (float)(peak-ith)/peak; }, maxs, stock);
    return 100.0f * ranges::max(dds);
}

 

Playing with patterns

Consider again the brute force solution:

int MaxDrawdownQuadratic(const vector<int>& stock)
{
    auto mdd = 0;
    for (auto j=0u; j<stock.size(); ++j)
    {
        for (auto i=j; i<stock.size(); ++i)
        {
            mdd = std::max(mdd, stock[j] - stock[i]);
        }
    }        
    return mdd;
}

We have seen that the optimal solution consists in just scanning the array forward and “caching” the biggest stock[j] so far.

A similar schema applies if we think the solution backwards: we scan the array backwards and cache the lowest price so far:

int MaxdrawdownBackwards(const vector<int>& stock)
{
    auto mdd = 0;
    auto minSoFar = stock.back();
    for (auto i=stock.size()-1; i>0; --i)
    {
        mdd = std::max(mdd, stock[i-1] - minSoFar);
        minSoFar = std::min(minSoFar, stock[i-1]);
    }
    return mdd;
}

Getting to the ranges-based solution is not so hard since we know how the problems is broken down into patterns: the forward cumulative maximum is replaced with the backward cumulative minimum. Still the prefix sum pattern. We just change the proper bits:

• stock is iterated backwards
• std::min displaces std::max

zip | map | reduce stays the same except for the inputs order (we have to subtract stock[i] to the i-th minimum) and the direction of stock (backwards).

Thus, here is the code:

int MaxDrawdownBackwards(const vector<int>& stock)
{
   auto mins = view::partial_sum(view::reverse(stock), [](auto l, auto r){ return std::min(l, r); });
   return ranges::max(view::zip_with(std::minus<>{}, view::reverse(stock), mins));
}

If you have some difficulties at this point, write down the “intermediate” STL code without ranges.

The same challenge gave us the opportunity to find another solution with the same patterns.

Playing with patterns is to programmers creativity as playing with colors is to painters creativity.

Playing with patterns is a productive training for our brain.

 

Problem variations

Playing with patterns is also useful for tackling problem variations fluently. For instance, if the problem changes to “calculate the minimum drawdown”, we just have to replace ranges::max with ranges::min. That’s possible because we know how the problem has been broken down into patterns.

The MDD problem has interesting variations that can be solved with the same patterns (customizing the proper bits). A couple of challenges are left to the willing reader:

• Given an array A, find the maximum difference A[j] - A[i] with i < j (MDD is j < i).
  Rephrasing: given a series of stock prices, find the maximum profit you can obtain by buying the stock on a certain day and selling it in a future day. Try your solutions here (alas, up to C++14).
• Given an array of stock prices, each day, you can either buy one share of that stock, sell any number of shares of stock that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy? See the full problem and try your solutions here (alas, up to C++14).

 

Have fun practicing with STL algorithms and ranges!