algorithm - 循环最长递增子序列

Question

如果数字以循环方式排列，如何找到最长递增子序列的长度。例如：

LIS of 3, 2, 1 is 3 [1, 2, 3].

PS 我知道如何在 O(nlogn) 中解决线性 LIS。

问题来源：https ://www.codechef.com/problems/D2/

更新：LIS 必须通过循环一次来计算。示例 2：LIS of 1, 4, 3是 2，可以是1, 3 or1, 4或3, 4。
谢谢

Answer 1

有问题的例子是错误的。[1,2,3] 的圆形旋转将是 [2,3,1] 或 [3,1,2]。

在这种情况下，我们可以用与最长递增子序列类似的方式来解决它。作为：

1. 按升序对列表进行排序。

2. 在原始列表中找到最小元素。

3. 从原始列表中的 min_index 开始迭代，并与排序列表进行比较，并创建与最长公共子序列相同逻辑的中间数组 L[i][j]。i 将从 min_index 变为 (i+n-1)%n
4. 最后返回 L[max_index][n]