算法实习涉及基因拼接工作。

简介：
随着基因组DNA序列数据的海量获取，对其进行基因研究变得愈发关键（基因组DNA是蛋白质合成的载体）。众所周知，在基因组序列中，由于存在非编码的DNA中断编码区，真核生物（相比于原核生物）的基因链呈现出更为复杂的结构。具体而言，一个基因通常会被分割成若干个编码片段，这些片段被称为外显子。尽管在蛋白质合成过程中外显子的排列顺序是固定的，但外显子的数量和长度却可以呈现出任意的组合。目前常用的基因识别算法通常包含两步：首先，寻找潜在的外显子；其次，通过寻找一条包含尽可能多外显子的基因链，从而尽可能地完成一个完整的基因的拼接。这条拼接的链条必须严格遵循外显子在基因组序列中出现的顺序。如果外显子i位于外显子j的前面，那么i的末尾位置必须位于j开头的位置之前。本题目的核心目标在于，给定一组可能的候选外显子集合，找出一条能够包含最多外显子片段的链条，并最终拼接成一个完整的基因。输入数据将提供一组实例，每个实例的开头将给出基因组序列中可能的外显子数量n（0 < n < 1000）。随后的n行将分别给出每对整数，它们代表了外显子在基因序列中的起始和结束位置。假设整个基因组序列的最长长度为50000。当一行中的数值为0时，表示输入数据的结束。输出部分对于每个实例而言，将输出最有可能包含最多外显子的链条以及该链条中对应的外显子信息，每行输出一条链。若存在多条具有相同数量外显子的链条时，则输出其中任意一条。以下是一个输入示例：6 3 4 0 5 2 2 1 3 6 作为输出示例：3 1 5 6 42 3 1 建议采用贪心算法或动态规划方法来解决该问题。