Max Drawdown with Minimum Window Length

Question

For a given time series of floats, it is pretty easy to calculate an unconstrained maximum drawdown in O(n) time, where max drawdown is defined as

\min_{i,j, i<j}(x_j - x_i)

In python, we the calculation is min(x - numpy.expanding_max(x)), but to get a O(n) algo write it explicitly:

def max_drawdown(s):
    drawdn = 0
    m,M = s[0],s[0]
    t1,t2 = 0,0
    T1,T2 = 0,0
    for i,v in enumerate(s):
        if (v < m):
            if (v-m) < drawdn:
                drawdn = v-m
                t2 = i
                T1,T2 = t1,t2
        else:
            m = v
            t1 = i
    return T1,T2,drawdn

Is there an O(n) algorithm for a max_drawdown that is constrained to have window duration > min_length? In this case I want \min_{i,j, (j-i) > min_length}(x_j - x_i).

Note that this is not a "rolling drawdown" calculation as in Compute *rolling* maximum drawdown of pandas Series.

Answer 1

The modifications are quite small compared to your max_drawdown function. The current algorithm can be written in pseudocode

Iterate over list
  if (current_element > maximum)
    maximum = current_element
  if (current element - maximum < drawdn)
    drawdn = current_element-maximum

Now instead of searching the max_drawdown at same index we search for the maximum value we need to have a distance of min_length with those indexes. In Python this becomes:

def max_drawdown_min_lenght(s,min_length):
    min_length += 1 #this is for i-j > l (not i-j >= l)
    drawdn = 0
    m = s[0]
    t1 = 0
    T1,T2 = 0,0
    for i in range(len(s)-min_length):
        if (s[i] >= m): #do we have new maximum?
            m = s[i]
            t1 = i
        if (s[i+min_length]-m) < drawdn:#do we have new max drawdown?
            drawdn = s[i+min_length]-m
            T1,T2 = t1,i+min_length
    return T1,T2,drawdn