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

What's a fast algorithm for finding the length of largest monotonically increasing sequence in an array of integers.

推荐答案

从维基百科：最长递增子（O（ N 的日志的 N 的））

From 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)