其实并不难,官方题解给的 dp 做法太吓人了
题解 #
首先定义一下“排了序的子序列”:它是一个原数组的子序列并且在排序之后的数组中是一个子数组。不难看出没用被移动过的元素会形成一个排了序的子序列。所以说如果我们找到最长的排了序的子序列那么答案就是最小的。
因为我们只关注数字的相对大小,我们可以压缩一下数字,这样写起来会简单一些。然后每个数组开一个数组存改数字的所有下标。
然后遍历所有数字,如果当前数字的最小下标大于之前数字的最大下标,那么这个数字的所有下标都可以加到当前的子序列里。否则我们需要重新开始一个子序列,以下两点需要注意:
-
当前数字的一部分也是可以被加到刚才的子序列里的,比如说1,2,2,1,2
,第二个 2 就可以加进去变成1,1,1,2
。
-
之前的数的一部分也可以被加到新的子序列里,比如1,2,2,1,2
,我们可以把第一个 1 加进来变成1,2,2,2
。
但是还有一种特殊的情况:这个子序列只包含两个数的下标,并且这两个数的下标都是不完整的,比如2,1,1,2,2,1
。不难看出我们要取第一个数的一个前缀,取第二个数的一个后缀,那么我们就可以枚举前缀的位置然后找到对应的后缀。
Code #