Compute maximum drawdown in one pass

Question

Maximum drawdown is the largest percentage drop from a running peak to a subsequent trough of an equity curve:

$\text{MDD} = \max_{i \le j} \frac{E_i - E_j}{E_i}$

where $E_i$ is the equity at time $i$ (assume all values positive).

equity = [100, 120, 90, 105, 60, 80]
-> 0.5          # peak 120 down to trough 60

Return the maximum drawdown as a fraction, in $O(n)$ time and $O(1)$ space. The naive all-pairs scan is $O(n^2)$ .

Accepted Answer

For each time j, the worst drawdown ending at j uses the highest peak seen so far. So sweep once, carrying the running maximum and updating the worst relative drop: Tracing the example: the running peak goes 100, 120, 120, 120, 120, 120; drawdowns per step are 0, 0, 0.25, 0.125, 0.5, 0.333..., answer 0.5. Time O(n), space O(1). Details interviewers probe: the peak must come before the trough (this sweep guarantees it, sorting or max(equity)/min(equity) do not); dividing by the current running peak (not the global max) is what makes each ratio a legitimate drawdown; and if the "equity" series …

Compute maximum drawdown in one pass

Your answer

More Coding questions