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)$ **Part 1.** Design an algorithm that, upon receiving each new $C_i$, updates the maximum drawdown in $O(1)$ time and $O(1)$ space. 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.