为了更好的介绍O(nlogn)算法,我们回顾一下一般的O(n^2)的算法。
令A[i]表示输入第i个元素,d[i]表示从A[1]到A[i]中以A[i]结尾的最长子序列长度。对于任意的0 < j <= i-1,如果A(j) < A(i),则A(i)可以接在A(j)后面形成一个以A(i)结尾的新的最长上升子序列。对于所有的 0 < j <= i-1,我们需要找出其中的最大值。
DP状态转移方程:d[i] = max{1, d[j] + 1} (j = 1, 2, 3, ..., i-1 且 A[j] < A[i])
①
对于最长不下降子序列,怎样实现O(nlogn)算法呢?我们知道O(n^2)的算法复杂度高的原因就在于要更新d[i]的值......
阅读全文