algorithm - 有人能解释一下为什么下面的 LIS 算法不是 O(n) 吗？

Question

以下代码遍历一次链表，找到LIS。我不明白为什么 DP 算法应该采用 O(n2)。

//C
int lis(int *a, int l){
  if(l == 0) return 1;
  else if(a[l] > a[l - 1])  return  1 + lis(a, l - 1);
  else  return lis(a, l - 1);
}

int main(){
  int a[] =  { 10, 22, 9, 33, 21, 50, 41, 60 };
  cout << lis(a, sizeof(a)/sizeof(a[0]) - 1);
}

% erlang
lis([_H]) -> 1;
lis([H1, H2 |T]) when H1 > H2 ->  1 + lis([H2|T]);
lis([_H|T]) -> lis(T).

main() ->  lis(lists:reverse([ 10, 22, 9, 33, 21, 50, 41, 60 ])).

Answer 1

lis/1 函数的当前实现是 O(n)，我看不出有任何怀疑的理由。但是有一些问题。您的实现实际上并未计算有效的 LIS。尝试

lis(lists:reverse([1,2,3,4,1,2]))

错误示例。最长递增序列是 [1,2,3,4]，对吧？但是您的算法返回 6 作为结果。

• 您的算法中的第一个错误是您每次都增加 result，当您遇到大于前一个的元素时。但是，只有当当前元素大于当前 LIS 的最大元素 时，您才应该增加 result。所以(根据上面的例子)你应该记住 4 并且在你检测到 2 大于 1 之后不要增加 result >.

• 但这不仅仅是您必须做的事情。考虑序列 1 2 3 6 4 5。对于 5 个第一个元素，LIS 的长度为 4。但是那里有两个可能的选项 - 1 2 3 4 或 1 2 3 6。您应该将哪个作为实际的 LIS？

• 等等等等......

另一个例子直接来自wiki page.

序列 [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] 有 LIS [ 0, 2, 6, 9, 13, 15](例如，6 元素)，但您的算法显示为 9。

而且，(请纠正我，如果我错了)，LIS 实现必须返回子序列本身，而不仅仅是它的长度。