首页 > 代码库 > 编程之美---求数组中最长递增子序列

编程之美---求数组中最长递增子序列

写一个时间复杂度尽可能低的程序,求一个一维数组(N个元素)中最长递增子序列的长度。

解法一:用动态规划,找出以当前元素结尾的最大递增子序列长度。dp[i+1] = max{1, dp[i]+1} ,array[i+1]>array[k] ,k<=i; 复杂度为o(n*n + n).

解法二:另外开一个数组保存长度为i的递增子序列的长度最大的最后一个元素最小的值,然后当处理数组中第i个元素时,从当前最大子序列的长度开始递减,依次寻找直到arrary[i]大于当前最大子序列长度的末尾元素值,然后更新第i个元素结尾的子序列的长度。如果当前最长序列大于最长递增序列长度,更新最长信息,否则看是否要更新因为array[i]的加入使得以array[i]为末尾元素的那些同样长度的子序列末尾元素值为最小。此方法复杂度仍为o(n*n).

解法三:因为在递增序列中,如果i<j,那么长度为i的子序列末尾元素值一定小于长度为j的末尾元素值。因此,对于寻找直到arrary[i]大于当前最大子序列长度的末尾元素值,可以采用二分的思想,于是复杂度降为o(n*logn)。

编程之美---求数组中最长递增子序列