[科普中国]-最长递增子序列

在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O(n log n)的时间复杂度，这里n表示输入序列的规模。

最长递增子序列问题问题描述：

给定正整数序列x1,···,xn。

（1）计算其最长递增子序列的长度s。

（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。

（3）如果允许在取出的序列中多次使用x1和 xn，则从给定序列中最多可取出多少个长度为s的递增子序列。12345。

编程任务：

设计有效算法完成（1）（2）（3）提出的计算任务1。

数据输入：

由文件input.txt提供输入数据。文件第1行有1个正整数n，表示给定序列的长度。接下来的1行有n个正整数x1,···,xn。

结果输出：

程序运行结束时，将任务（1）（2）（3）的解答输出到文件 output.txt中。第1 行是最长递增子序列的长度s。第2行是可取出的长度为s的递增子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s的递增子序列个数。

输入文件示例：

input.txt 43 6 2 5输出文件示例：

output.txt223与其他算法问题的关系最长的子序列问题与最长公共子序列问题密切相关，后者具有二次时间动态规划解：序列S的最长增长子序列是S和T的最长公共子序列，其中T是排序S的结果但是，对于输入是整数1,2，...，n的排列的特殊情况，这种方法可以更有效，导致形式O的时间范围（n log log n）。

置换图中最大的集团由定义图的置换的最长递减子序列定义;最长的递减子序列在计算复杂度上等同于所有数字的否定，等于最长的增加子序列。因此，可以使用增长最长的子序列算法在置换图中有效地解决集团问题。

在置换与Young tableaux之间的Robinson-Schensted对应关系中，对应于置换的画面的第一行的长度等于置换的最长增加子序列的长度，并且第一列的长度等于最长的长度。减少子序列。

高效的算法下面概述的算法通过数组和二进制搜索有效地解决了增长最长的子序列问题。它按顺序处理序列元素，保持到为止发现的最长的增长子序列。将序列值表示为X[0]，X[1]等。然后，在处理X[i]之后，算法将存储两个数组中的值：

M[j]----存储最小值X[k]的索引k，使得在范围k≤i上存在以X[k]结尾的长度j的增加子序列。注意，j≤（i + 1），因为j≥1表示增加子序列的长度，k≥0表示其终止的索引。

P[k]----将X[k]的前驱者的索引存储在以X[k]结尾的最长增加子序列中。

此外，该算法存储变量L，该变量L表示为止发现的最长增长子序列的长度。因为下面的算法使用从零开始的编号，为了清楚起见，M用M[0]填充，其未被使用，使得M[j]对应于长度为j的子序列。真正的实现可以跳过M[0]并相应地调整索引。

注意，在算法的任何一点，序列X[M[1]]，X[M[2]]，...，X[M[L]]

在增加。因为，如果在X [M[j]]处结束的长度j≥2的子序列越来越多，那么也存在以较小值结束的长度j-1的子序列：即以X [P[M]结束的一个子序列[J]]]。因此，我们可以在对数时间内以此顺序进行二进制搜索。

然后，算法进行如下：

P = array of length N M = array of length N + 1 L = 0 for i in range 0 to N-1: // Binary search for the largest positive j ≤ L // such that X[M[j]]