Garsia Wachs
目录
- 找到满足 $q_{k-1} \lt q_{k+1}$ 的最小下标 $k$
- 找到满足 $q_{j-1} \gt q_{k-1} + q_k$ 的最大 $j \lt k$
- 从列表中清除 $q_{k-1}, q_k$
- 在 $q_{j-1}$ 之后插入 $q_{k-1} + q_k$
- $q_{-1}$ 和 $q_{n+1}$可以用 $\infty$ 处理
| $q-1$ | $q0$ | $q1$ | $q2$ | $q3$ | $q4$ | $q5$ | $k$ | $j$ |
|---|---|---|---|---|---|---|---|---|
| $\infty$ | 186 | 64 | 35 | 32 | 103 | $\infty$ | 3 | 1 |
| $\infty$ | 186 | 67 | 64 | 103 | $\infty$ | 2 | 1 | |
| $\infty$ | 186 | 131 | 103 | $\infty$ | 2 | -1 | ||
| $\infty$ | 234 | 186 | $\infty$ | 1 | -1 | |||
| $\infty$ | 420 | $\infty$ |