背景：

这个问题来自于基因组学领域，特别是关于比较不同物种染色体上基因的顺序。在进化过程中，染色体上的基因通过重排变化，我们可以通过比较两个物种的染色体上基因的顺序来研究它们的进化关系。

问题的核心是找到两个染色体上相同顺序的最大基因集合。这可以通过考察基因的排列来实现。假设两个染色体共享n个基因，我们可以将一个染色体上的基因按照出现的顺序用数字1到n来标记，那么第二个染色体上的基因排列可以被视为这些数字的一个排列。为了找到顺序相同的最大基因集合，我们只需要在这个排列中找到最长的递增元素集合。

算法我们使用动态规划。

1. 初始化：

   • 序列：5 1 4 2 3

   • 初始化 lengths 数组，每个元素表示以当前位置结束的最长递增子序列的长度。初始时，所有位置的长度都设置为 1，因为每个元素自身至少构成一个长度为 1 的递增子序列。

   • lengths = [1, 1, 1, 1, 1]，一定要注意这个数组的定义！这个数组的定义为，到目前这个元素为止，前面最长的的递增子序列的长度！

2. 计算最长递增子序列的长度：

   • 对于第一个元素（5），没有之前的元素可以比较，所以保持 lengths[0] = 1。

   • 对于第二个元素（1），它小于5，无法形成递增序列，所以 lengths[1] = 1。

   • 对于第三个元素（4），它大于1，因此可以形成一个长度为2的递增子序列（1, 4）。我们更新 lengths[2] = max(lengths[2], lengths[1] + 1) = max(1, 1 + 1) = 2。

   • 对于第四个元素（2），它大于1但小于4，因此可以形成一个长度为2的递增子序列（1, 2）。我们更新 lengths[3] = max(lengths[3], lengths[1] + 1) = max(1, 1 + 1) = 2。

   • 对于第五个元素（3），它大于2，因此可以形成一个长度为3的递增子序列（1, 2, 3）。我们更新 lengths[4] = max(lengths[4], lengths[3] + 1) = max(1, 2 + 1) = 3。

3. 重建最长递增子序列：

   • 最终，lengths 数组为 [1, 1, 2, 2, 3]，表示最长递增子序列的长度为3，结束于序列的最后一个元素。

   • 为了重建这个子序列，我们从后向前遍历，寻找长度递减的元素。我们找到3、2、1，因此最长递增子序列是 1, 2, 3。

最长递减的很好写，我们将数组倒过来求一个最长递增子序列。

代码：

def longest_increasing_subsequence(sequence):if not sequence:return []lengths = [1] * len(sequence)for i in range(1, len(sequence)):for j in range(i):if sequence[i] > sequence[j]:lengths[i] = max(lengths[i], lengths[j] + 1)max_length = max(lengths)lis = []for i in range(len(sequence) - 1, -1, -1):if lengths[i] == max_length:lis.append(sequence[i])max_length -= 1return lis[::-1]def longest_decreasing_subsequence(sequence):return longest_increasing_subsequence(sequence[::-1])file_path = ''
with open(file_path, 'r') as file:lines = file.readlines()combined_sequence = ' '.join(lines[1:])sample_sequence = list(map(int, combined_sequence.split()))lis = longest_increasing_subsequence(sample_sequence)
lds = longest_decreasing_subsequence(sample_sequence)print(' '.join(map(str, lis)))
print(' '.join(map(str, lds[::-1])))