HIGHEST calculates the maximum value over a rolling lookback window. This O(1) amortized streaming implementation uses a monotonic deque algorithm, enabling real-time updates without re-scanning the entire window. Validated against TA-Lib MAX and Tulip max functions.
## Historical Context
Rolling maximum is a foundational concept in technical analysis, underpinning Donchian Channels, breakout detection, and trailing stop calculations. The naive approach scans all values in the window on each update—O(n) per bar. For a 200-period window processing 10,000 bars, that's 2 million comparisons.
The monotonic deque algorithm reduces this to O(1) amortized time by maintaining a decreasing sequence of candidates. Only values that could potentially be the maximum are kept; smaller values that can never become maximum (because they'll expire before the larger values) are discarded.
QuanTAlib implements this optimal algorithm with full streaming support, SIMD batch optimization, and proper state management for bar corrections.
## Architecture & Physics
### 1. Monotonic Deque
The core data structure is a deque maintaining indices of values in monotonically decreasing order:
\text{Highest}_t = \max(V_0, V_1, \ldots, V_t) \quad \text{for } t < n
$$
### Complexity Analysis
| Operation | Naive | Monotonic Deque |
| :--- | :---: | :---: |
| Per-update (worst) | O(n) | O(n) |
| Per-update (amortized) | O(n) | O(1) |
| Total for N updates | O(N×n) | O(N) |
Each element is pushed and popped from the deque at most once across all operations.
## Performance Profile
### Operation Count (Streaming Mode, Amortized)
| Operation | Count | Cost (cycles) | Subtotal |
| :--- | :---: | :---: | :---: |
| CMP (expired check) | 1 | 1 | 1 |
| CMP (monotonicity) | ~2 avg | 1 | 2 |
| Array access | 3 | 3 | 9 |
| Index arithmetic | 2 | 1 | 2 |
| **Total** | **~8** | — | **~14 cycles** |
### Batch Mode (SIMD)
For batch processing, SIMD can parallelize comparisons within segments. However, the monotonic deque's sequential nature limits full vectorization. The span-based Calculate method uses a stackalloc deque buffer for cache efficiency.
1.**Window Boundary Effects**: Maximum changes abruptly when the previous max expires from the window. This creates step changes in the output.
2.**Warmup Period**: `IsHot` becomes true after `period` values. Before warmup, returns maximum of available data.
3.**Memory Footprint**: O(n) memory for both the ring buffer and deque indices. For period=200: ~3.2KB (200 doubles + 200 ints).
4.**Deque Rebuild on Correction**: When `isNew=false`, the entire deque is rebuilt by scanning the buffer. Frequent corrections are O(n) each.
5.**Large Periods**: For very large periods (>1000), consider segment trees or sparse tables if corrections are rare. The deque approach optimizes for the streaming case.
6.**Using isNew Incorrectly**: Use `isNew: false` only when correcting the current bar. New bars must use `isNew: true`.
## References
- Tarjan, Robert E. (1985). "Amortized Computational Complexity." SIAM Journal on Algebraic Discrete Methods.
- Lemire, Daniel. (2006). "Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element."
