如何在循环缓冲区中寻找最长递增子序列（LIS）？

核心思路 #

循环缓冲区的LIS包含两种场景：

• 子序列不跨首尾：对应普通数组的LIS，用标准O(n log n)算法计算即可。
• 子序列跨首尾：子序列从数组末尾选取部分元素，再从数组开头选取部分元素，保持严格递增。这种场景可以通过将原数组拼接为自身（arr + arr），在长度为2n的新数组中寻找长度不超过n的LIS来覆盖。

高效解法步骤 #

1. 特殊情况处理：
   • 若数组所有元素相同，严格递增规则下LIS长度为1；若非严格递增（允许元素相等），则长度为n。
2. 拼接数组计算LIS：
   • 将原数组拼接为arr + arr，使用标准O(n log n)的LIS算法计算该数组的LIS长度。
   • 由于循环缓冲区的元素总数为n，最终循环LIS长度取计算结果与n的较小值（避免出现超过n的无效结果，比如严格递增数组拼接后LIS长度为2n，实际有效长度为n）。
3. 获取最终结果：
   • 拼接数组的LIS计算结果已包含普通LIS的情况，因此最终结果为min(拼接数组的LIS长度, n)。

实例验证（以序列5, 3, 4, 2, 1为例） #

• 拼接后的数组为[5,3,4,2,1,5,3,4,2,1]。
• 用O(n log n)算法计算LIS，得到长度为3（对应子序列1,3,4或2,3,4）。
• 取min(3,5)=3，与预期结果一致。

算法复杂度分析 #

拼接后的数组长度为2n，标准O(n log n)算法的时间复杂度为O(2n log 2n)，等价于O(n log n)，远优于暴力枚举所有排列的O(n²)解法。

标准O(n log n) LIS算法实现要点 #

维护一个tails数组，其中tails[i]表示长度为i+1的递增子序列的最小末尾元素：

• 遍历每个元素x：
  • 若x大于tails的最后一个元素，直接追加到tails末尾。
  • 否则，找到tails中第一个大于等于x的元素，用x替换它。
• 最终tails的长度即为LIS的长度。

内容的提问来源于stack exchange，提问作者ismbks