如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~

題目：

最長遞增子序列

Given: A positive integer n (n<10,000) followed by a permutation π of length n.

所給：不超過10,000的一個正整數(shù)n，以及一個長度為n的排列π。

Return: A longest increasing subsequence of π, followed by a longest decreasing subsequence of π.

需得：π的最長遞增子序列和最長遞減子序列。

?

測試數(shù)據(jù)

5

5 1 4 2 3

測試輸出

1 2 3

5 4 2

?

背景

最長遞增子序列是給定序列中最長、嚴(yán)格遞增的子序列（不要求連續(xù)），例如序列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，學(xué)生信】19 枚舉基因排列順序中我們已經(jīng)知道，在進(jìn)化親緣關(guān)系相近的物種通常具有相近的基因結(jié)構(gòu)，通過比較這些結(jié)構(gòu)間的重排和相似現(xiàn)象，可以幫助我們理解物種間的關(guān)系。

尋找數(shù)量盡量大的一組方向相同的基因是研究兩個結(jié)構(gòu)相似的染色體上基因最簡單的方法之一，即相當(dāng)于在第二條染色體上找第一條染色體基因序列的最長遞增子序列。

?

思路

本題可以有多種算法解決，這里使用動態(tài)規(guī)劃法。動態(tài)規(guī)劃是一種經(jīng)典算法，主要思路是把一個問題分成若干個小問題來解決。動態(tài)規(guī)劃的整個過程可以劃為四個部分：

1）存儲子問題的最優(yōu)化的動態(tài)規(guī)劃矩陣；

2）最優(yōu)化的遞歸計(jì)算方法；

3）給出子問題最優(yōu)解的矩陣填充過程；

4）尋找最優(yōu)化比對路徑的回溯方法。

?

以測試數(shù)據(jù)為例求最長遞增序列

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個數(shù)字順序組成的序列，第一列為測試數(shù)據(jù)所給的排列5 1 4 2 3

2）給出遞歸計(jì)算方法：

這里的核心思路是在序列中找一個位置作為這之前序列的最長遞增子序列的結(jié)尾字符，再掃描這個位置之前的字符，找到使該子序列為最長遞增子序列的序列，即找到所有可以把該位置字符加入的子串中最長的一個，由此形成遞歸。

3）填充矩陣

把給定位置之前的每一個元素都寫成串，添加一個新元素時就從已有的串中找出最優(yōu)的，同時記錄長度，如下表：

[['', 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）最優(yōu)路徑回溯

找到長度最長的子串，回溯讀出序列，再逆序即得到目標(biāo)子串：

[['', 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]
??? # 計(jì)算過程
??? 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

# 讀入數(shù)據(jù)
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

# 將數(shù)據(jù)代入函數(shù)，接受最長子串

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()