找出由n个数组成的序列的最长单调递增子序列

原博客地址

解法一：转化成LCS问题求解，时间复杂度为O(n*n).

思路：原序列为A，把A按升序排序得到序列B，求出A，B序列的最长公共子序列，即为A的最长单调递增子序列。

解法二：设d[i]为以第i个元素结尾的最长递增子序列的长度，则d[i]=max{0,d[j] | j<i, a[j] <a[i]}, ans = max{ d[i] }，时间复杂度O(n*n)

解法三：

    设d[i]为以第i个元素结尾的最长递增子序列的长度。假设已经计算出的两个状态p和q满足a[p]p且i>q)来说，p一定比q好。所以此时只保留p一定不会丢失最优解。所以对于相同的d值，只需保留a[i]最小的一个。g[i]表示d值为i的最小状态编号(g[i]初始化为正无穷)。

    在给定状态 i 时,可用二分查找找到满足g[k]>=a[i]的第一个下标k,d[i]=k,此时a[i] <g[k]而d[i]=k,所以更新g[k]=a[i]，时间复杂度O(nlogn).