test100.txt

时间复杂度为O(nlogn)的最长单调递增子序列问题的计算程序。不是动态规划算法。在一分钟之内可以计算n=10^6个元素的递增子序列。

100
35 59 48 5 76 50 89 77 71 52 67 54 16 60 100 30 43 91 49 24 25 76 15 15 41 89 0 58 86 17 79 95 100 93 38 31 0 6 37 89 88 2 38 5 15 93 64 89 71 95 41 3 9 94 58 89 26 78 31 93 46 35 88 21 22 35 64 77 84 17 16 8 71 95 68 9 56 89 72 29 26 16 4 8 100 34 95 97 57 76 87 95 67 70 39 45 80 77 68 36