先特判一些 trivial 的情形：LIS 和 LDS 都单调不降，且变化量之和不能超过 1。

考虑一个二维网格 $(r, c)$，将整个网格向右微微旋转小角度 后，视横坐标为数组下标，纵坐标为排列的值，可以定义为 $V(r, c) = r \cdot N - c$。这是因为同一行越往右走，高度微微下降（$c$ 的权重为 $-1$），上一行到下一行，高度大幅陡峭上升（$r$ 的权重为 $+N$）。

现在，选不同行的点构成上升子序列，同一行往右走构成下降子序列。即 行数决定 LIS，列数决定 LDS。

• 若 LIS 增加 1：必须扩展网格的总行数，在最下方开辟新的一行；
• 若 LDS 增加 1：必须扩展网格的最大宽度。在第 $1$ 行的最右侧追加一个点；
• 否则，不能增加最大行数，也不能超过第 $1$ 行的长度，那就在网格里面塞点。如果塞满了就无解 $^\dagger$。

最后，将权值函数 $V(r, c) = r \cdot N - c$ 离散化即可。

$\dagger$: 这是因为 Erdős–Szekeres Theorem——任意长度至少为 $(r-1)(s-1) + 1$ 的排列中，必存在一个长度为 $r$ 的 LIS，或一个长度为 $s$ 的 LDS。换言之，若排列的 LIS 长度为 $r$，LDS 长度为 $s$，那么排列的长度不能超过 $r s$。