A totally monotone matrix has a non-decreasing staircase of row minima. SMAWK finds them all via REDUCE (drop dead columns) + INTERPOLATE (recurse even rows, fill odd).
| Method | Time |
|---|---|
| Brute force (all cells) | O(n·m) |
| Divide & conquer (sib. 12) | O((n+m) log n) |
| SMAWK (this) | O(n + m) |
| One DP layer (SMAWK) | O(n) |
| K-layer DP (SMAWK) | O(K·n) |
Precondition: matrix is totally monotone (Monge ⟹ TM). Otherwise the answer is silently wrong.