algorithm - 找出最大递增序列的长度

Question

在整数数组中查找最大单调递增序列的长度的快速算法是什么。

Answer 1

来自 Wikipedia: Longest increasing subsequence (O(n log n))

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)