一个序列中的一部分(不要求连续)组成的序列称为子序列o所谓的递增子序 列:首先它是子序列,其次它们的元素是递增的o而最长子序列就是子序列中元素的个数 是最多的那一序列o例如,dabdbf 的最长递增子序列是abdf o请设计一个基于动态规 划的O(n log n) 算法来找出序列A[1..n]中的最长子序列o

首先，我们需要定义一个数组dp，其中dp[i]表示以A[i]为结尾的最长递增子序列的长度。

接下来，我们需要一个变量len来记录当前最长递增子序列的长度，并且初始化为1。同时，我们还需要一个变量tail，表示目前已经构建的最长递增子序列的最后一个元素。

然后，我们从第二个元素开始遍历整个序列A。对于每个元素A[i]，我们需要找到在它之前的所有元素中，比它小的元素中最长的递增子序列，然后把A[i]接到这个子序列后面。这样，我们就可以得到以A[i]为结尾的最长递增子序列。

具体来说，我们可以使用二分查找来找到在A[1...i-1]中比A[i]小的元素中最长的递增子序列。在查找过程中，我们需要维护一个tails数组，其中tails[k]表示长度为k的递增子序列的最后一个元素的最小值。对于每个A[i]，我们都要在tails数组中找到第一个大于等于它的元素，然后用它来更新dp[i]和tails数组。

最终，最长递增子序列的长度就是dp数组中的最大值。

下面是具体的算法实现：

def findLongestIncreasingSubsequence(A):
    n = len(A)
    dp = [1] * n
    tails = [A[0]]

    for i in range(1, n):
        if A[i] < tails[0]:
            tails[0] = A[i]
        elif A[i] > tails[-1]:
            tails.append(A[i])
        else:
            l, r = 0, len(tails) - 1
            while l < r:
                mid = (l + r) // 2
                if tails[mid] < A[i]:
                    l = mid + 1
                else:
                    r = mid
            tails[l] = A[i]
        dp[i] = len(tails)

    return max(dp)

这个算法的时间复杂度是O(n log n)，其中n是序列A的长度。