algorithm - 在数组中查找 1 ... k 的最长排列？

Question

给定一个 N 个整数序列。如何找到形成排列的相邻数字的最长子序列的长度。我只找到了 O(N^2) 算法。我认为应该有 O(NlogN) 甚至 O(N) 的解决方案。请推荐其中任何一个。

这个序列 1 3 1 2 5 的答案是 3 (4 1 3 1 2 5 )

这是 SPOJ 问题 LPERMUT .

O(N^2) 算法

Foreach i find the sum of first i elemetns: Sum(i)

Foreach i find the last element with indexes 1 .. i-1 which is equal to i-rd element: Prev(i)

Foreach i iterate j throw i+1 .. N while Prev(j) equals between i and j. 
//So we get that all elemnent between i and j are distinct. 

Then check if sum of them is equal to 1+2+...(j-i+1). 
    If it occurs that elements are permutation. 
    Sum of the elements between i and j we can get by Sum(j) - Sum(i-1)

Answer 1

可以使用贪心算法

Input: ListOfElements={el_1, el_2,...,el_N}
permutation<-{}
while(dimension(size(permutation)<DesiredSize)
{
  while(VerifyIfIsPermutation(permutation U el)=false)
   el<-SelectAnElementFromList(ListOfElements)
}
print permutation

该算法具有 O(n^2) 复杂度。如果以前对数组进行排序，则可以降低这种复杂性。另一种生成排列的方法是对该列表使用随机洗牌。此外，您可以在元素之间使用多次旋转，从而保证不会重复生成的排列。