考虑值域上的两个元素 。如果 都有 为真，那么可以使得 向 连一条边，表示 在最长公共子序列 中也是 。

因为是在值域上的点之间连边，且是从位置小的值域向位置大的值域连边（没有位置大向位置小的连边），那么不会产生环，也就是有向无环图。

在有向无环图上的任意一条路径都是 个排列的一个 ，那么在有向无环图上跑一个最长路 即可。