【ROSALIND】【练Python，学生信】24 求解最长递增子序列
如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面 谢谢配合~
题目：
最长递增子序列
Given: A positive integer n (n<10,000) followed by a permutation π of length n.
所给：不超过10,000的一个正整数n，以及一个长度为n的排列π。
Return: A longest increasing subsequence of π, followed by a longest decreasing subsequence of π.
需得：π的最长递增子序列和最长递减子序列。
测试数据
5
5 1 4 2 3
测试输出
1 2 3
5 4 2
背景
最长递增子序列是给定序列中最长、严格递增的子序列（不要求连续），例如序列2 50 4 30 6 8 10 12 22 14 16 18 17 20的最长递增子序列为2 4 6 8 10 12 14 16 17 20。
从【ROSALIND】【练Python，学生信】19 枚举基因排列顺序中我们已经知道，在进化亲缘关系相近的物种通常具有相近的基因结构，通过比较这些结构间的重排和相似现象，可以帮助我们理解物种间的关系。
寻找数量尽量大的一组方向相同的基因是研究两个结构相似的染色体上基因最简单的方法之一，即相当于在第二条染色体上找第一条染色体基因序列的最长递增子序列。
思路
本题可以有多种算法解决，这里使用动态规划法。动态规划是一种经典算法，主要思路是把一个问题分成若干个小问题来解决。动态规划的整个过程可以划为四个部分：
1）存储子问题的最优化的动态规划矩阵；
2）最优化的递归计算方法；
3）给出子问题最优解的矩阵填充过程；
4）寻找最优化比对路径的回溯方法。
以测试数据为例求最长递增序列
1）首先建立存储矩阵：
[['', 0], ['1', 0], ['2', 0], ['3', 0], ['4', 0], ['5', 0]]
[['5', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]]
[['1', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]]
[['4', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]]
[['2', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]]
[['3', 0], ['', 0], ['', 0], ['', 0], ['', 0], ['', 0]]
可以看到，矩阵第一行为1-5这5个数字顺序组成的序列，第一列为测试数据所给的排列5 1 4 2 3
2）给出递归计算方法：
这里的核心思路是在序列中找一个位置作为这之前序列的最长递增子序列的结尾字符，再扫描这个位置之前的字符，找到使该子序列为最长递增子序列的序列，即找到所有可以把该位置字符加入的子串中最长的一个，由此形成递归。
3）填充矩阵
把给定位置之前的每一个元素都写成串，添加一个新元素时就从已有的串中找出最优的，同时记录长度，如下表：
[['', 0], ['1', 0], ['2', 0], ['3', 0], ['4', 0], ['5', 0]]
[['5', 0], ['↑', 0], ['↑', 0], ['↑', 0], ['↑', 0], ['↖', 1]]
[['1', 0], ['↖', 1], ['←', 1], ['←', 1], ['←', 1], ['↑', 1]]
[['4', 0], ['↑', 1], ['↑', 1], ['↑', 1], ['↖', 2], ['←', 2]]
[['2', 0], ['↑', 1], ['↖', 2], ['←', 2], ['↑', 2], ['↑', 2]]
[['3', 0], ['↑', 1], ['↑', 2], ['↖', 3], ['←', 3], ['←', 3]]
4）最优路径回溯
找到长度最长的子串，回溯读出序列，再逆序即得到目标子串：
[['', 0], ['1', 0], ['2', 0], ['3', 0], ['4', 0], ['5', 0]]
[['5', 0], ['↑', 0], ['↑', 0], ['↑', 0], ['↑', 0], ['↖', 1]]
[['1', 0], ['↖', 1], ['←', 1], ['←', 1], ['←', 1], ['↑', 1]]
[['4', 0], ['↑', 1], ['↑', 1], ['↑', 1], ['↖', 2], ['←', 2]]
[['2', 0], ['↑', 1], ['↖', 2], ['←', 2], ['↑', 2], ['↑', 2]]
[['3', 0], ['↑', 1], ['↑', 2], ['↖', 3], ['←', 3], ['←', 3]]
1 2 3
最大递减子串的方法相同，矩阵如下：
[['', 0], ['5', 0], ['4', 0], ['3', 0], ['2', 0], ['1', 0]]
[['5', 0], ['↖', 1], ['←', 1], ['←', 1], ['←', 1], ['←', 1]]
[['1', 0], ['↑', 1], ['↑', 1], ['↑', 1], ['↑', 1], ['↖', 2]]
[['4', 0], ['↑', 1], ['↖', 2], ['←', 2], ['←', 2], ['↑', 2]]
[['2', 0], ['↑', 1], ['↑', 2], ['↑', 2], ['↖', 3], ['←', 3]]
[['3', 0], ['↑', 1], ['↑', 2], ['↖', 3], ['↑', 3], ['↑', 3]]
5 4 2
（或5 4 3）
代码
def LCS(s1, s2):
"""获得最长公共子序列"""
n = len(s1)
# 初始化矩阵元素
square = [[["", 0] for j in list(range(n+1))] for i in list(range(n+1))]
for i in list(range(1, n+1)):
square[i][0][0] = s1[i - 1]
for j in list(range(1, n+1)):
square[0][j][0] = s2[j - 1]
# 计算过程
for i in list(range(1, n+1)):
for j in list(range(1, n+1)):
if s1[i - 1] == s2[j - 1]:
square[i][j] = ['↖', square[i - 1][j - 1][1] + 1]
elif square[i][j - 1][1] > square[i - 1][j][1]:
square[i][j] = ['←', square[i][j - 1][1]]
else:
square[i][j] = ['↑', square[i - 1][j][1]]
i = 0
while i <=n:
# print(square[i])
i += 1
s3 = []
i = n
j = n
# 回溯并记录最长子串
while i > 0 and j > 0:
if square[i][j][0] == '↖':
s3.append(square[i][0][0])
i -= 1
j -= 1
elif square[i][j][0] == '←':
j -= 1
elif square[i][j][0] == '↑':
i -= 1
s3 = s3[::-1]
return s3
# 读入数据
f = open('input.txt', 'r')
input = f.readlines()
f.close()
n = int(input[0])
pie = ''.join(input[1])
pie = pie.split(' ')
i = 1
y1 = []
y2 = []
while i <= n:
y1.append(str(i))
y2.append(str(n-i+1))
i += 1
# 将数据代入函数，接受最长子串
inseq = ' '.join(LCS(pie, y1))
deseq = ' '.join(LCS(pie, y2))
f = open('output.txt', 'a')
f.write(inseq + '\n')
f.write(deseq + '\n')
f.close()
