Streaming Maximum Drawdown With Rolling Window
You are running a real-time risk dashboard for a single-asset trading strategy. As each trade $i$ arrives, it updates the cumulative P&L to a value $C_i$. You need to continuously report the maximum drawdown so far -- that is, the largest peak-to-trough decline in cumulative P&L observed up to the current trade.
Formally, after $n$ trades the maximum drawdown is:
$$\text{MDD}_n = \max_{1 \le j \le k \le n} (C_j - C_k)$$
Required function. Implement running_max_drawdown(C) where C is the list of cumulative P&L values (C[i] is the cumulative P&L after trade i). Return a list whose i-th entry is the maximum drawdown observed over C[0..i] inclusive. The result has the same length as C, every entry is non-negative, and the first entry is always 0.
Part 1. Design an algorithm that, upon receiving each new $C_i$, updates the maximum drawdown in $O(1)$ time and $O(1)$ space, and returns the running list of maximum drawdowns. Prove that your algorithm is correct.
Part 2. Now suppose you only care about the maximum drawdown over the last $M$ trades (a rolling window). Design a data structure that maintains this rolling-window maximum drawdown with $O(\log M)$ or better time per update. Discuss the trade-offs between time and space for different data structure choices.
Example
running_max_drawdown([0, 10, 4, 8, 2]) -> [0, 0, 6, 6, 8]
The peak reaches 10 at index 1; at index 2 the value drops to 4 (drawdown 6), and by index 4 the value is 2, a decline of 8 from that peak of 10 -- so the running max drawdown ends at 8.
Hints
- The maximum drawdown at any point is determined by the highest peak seen before the current time minus the current value. What two quantities do you need to track?
- For the streaming case, think about decomposing $\max_{j \le k}(C_j - C_k)$ as $\max_k(\max_{j \le k} C_j - C_k)$. Each factor is a running max that updates in $O(1)$.
- For the rolling window, consider a segment tree where each node stores (maxVal, minVal, maxDD). The key merge rule is: $\text{maxDD}_{\text{parent}} = \max(\text{maxDD}_L, \text{maxDD}_R, \text{maxVal}_L - \text{minVal}_R)$.
Worked Solution
How to Think About It: Maximum drawdown is the biggest drop from any peak to a subsequent trough. Track the running peak of cumulative P&L; after each new trade the *current* drawdown is peak_so_far - current_value. The maximum drawdown observed up to trade i is the largest current drawdown seen so far. Both the peak and the running max are O(1) updates, so we produce the whole answer list in a single O(n) pass.
Contract: Implement running_max_drawdown(C). C[i] is the cumulative P&L after trade i. Return a list whose i-th entry is the maximum drawdown observed over C[0..i] inclusive (a running max drawdown, not a single scalar). Drawdowns are non-negative; the first entry is always 0.
Algorithm (Part 1):
Maintain two scalars while scanning left to right: - peak: the running maximum of all C_j seen so far - max_dd: the maximum drawdown seen so far
On each new value c:
peak = max(peak, c)dd = peak - cmax_dd = max(max_dd, dd)- Append
max_ddto the output list.
Proof of Correctness: At step i, peak = max(C_0, ..., C_i), so dd_i = max_{j<=i} C_j - C_i is the deepest drawdown ending exactly at i. Since $$\max_{j \le k \le i}(C_j - C_k) = \max_{k \le i}\Big(\max_{j \le k} C_j - C_k\Big) = \max_{k \le i} dd_k,$$ accumulating the running max of dd_k yields the maximum drawdown over C[0..i]. $\square$
```python def running_max_drawdown(C): # C[i] is the cumulative P&L after trade i. # Return a list whose i-th entry is the maximum drawdown # observed over C[0..i] inclusive. result = [] peak = float('-inf') max_dd = 0 for c in C: if c > peak: peak = c dd = peak - c if dd > max_dd: max_dd = dd result.append(max_dd) return result ```
Algorithm (Part 2) -- Rolling Window (last M trades): The window version is harder because the peak can *expire* when it leaves the window, so a plain running max breaks. Use a segment tree over a circular buffer of size M, where each node stores maxVal, minVal, and maxDD, merged by $$\text{maxDD}_{\text{parent}} = \max(\text{maxDD}_L,\ \text{maxDD}_R,\ \text{maxVal}_L - \text{minVal}_R),$$ giving O(log M) worst-case per update and O(M) space. A monotone two-stack deque carrying the same (max, min, maxDD) aggregate achieves O(1) amortized per update but occasionally rebuilds in O(M). For a latency-sensitive risk dashboard the segment tree's worst-case guarantee is preferable; the deque is simpler when average throughput dominates.
Complexity (Part 1): O(n) total, O(1) state per update (excluding the output list).
Intuition
Maximum drawdown is the risk metric that keeps traders up at night -- it measures the worst peak-to-trough loss your strategy has experienced. The streaming version is deceptively simple: since drawdowns only happen from past peaks to the current value, you just need a running peak and a running max of (peak - current). Two variables, two comparisons per update, done. The deeper insight is that this works because in the all-history version, the peak never decreases -- it is a monotone quantity.
The rolling window version is where things get interesting, and it illustrates a fundamental pattern in streaming algorithms: when elements can both enter and leave your window, simple running aggregates break down. You need a data structure that supports efficient insertion, deletion, and query. The segment tree merge rule -- combining left-max, right-min, and child drawdowns -- is a beautiful example of how you can maintain a non-trivial aggregate (max over all $j < k$ pairs) by decomposing it into composable summaries. This same decomposition pattern shows up constantly in real-time risk systems: rolling Sharpe ratios, streaming VaR, and any metric that depends on order within a window.