問題の説明#
与えられた長さ の整数列 から、要素が厳密に増加し、かつ長さが最も長い部分列を求めます。時には、この最長部分列を復元することも求められます。
ケース：
A = [10, 9, 2, 5, 3, 7, 101, 18]
LIS = [2, 3, 7, 101] # 長さは 4
アプリケーションシーン#
生物情報学における DNA 配列構造の分析
株式分析における上昇トレンドの探索
ロボットの経路計画における列の最適制御
解法 1：動的計画法#
考え方： を第 個の要素で終わる最長上昇部分列の長さと定義し、初期値はすべて 1 とします。
状態遷移方程式：
def LIS_DP(A):
n = len(A)
dp = [1] * n
for i in range(n):
for j in range(i):
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
時間計算量：
空間計算量：
LIS 列を返すことができます。
解法 2：貪欲法 + 二分探索#
考え方：配列 tail を維持し、すべての長さ k の上昇部分列の中で最小のものの末尾要素を表します。
各数 x に対して、tail の中で最初に x 以上の位置 i を探します。
見つかった場合は、x を に置き換えます（貪欲法、より小さい末尾の方がより長い上昇部分列を拡張する可能性が高いため）。
見つからなかった場合（つまり、x がすべての要素より大きい場合）、x を tail の末尾に追加します。
最終的に、len (tail) が最長上昇部分列の長さになります。
ケースの説明
A = [10, 9, 2, 5, 3, 7, 101, 18]
tail = []
# tail の変化
10 → [10]
9 → [9]
2 → [2]
5 → [2, 5]
3 → [2, 3]
7 → [2, 3, 7]
101 → [2, 3, 7, 101]
18 → [2, 3, 7, 18]
# 結論 LIS の長さは 4
擬似コード：
import bisect
def LIS_binary_search(A):
tail = []
for x in A:
i = bisect.bisect_left(tail, x)
if i == len(tail):
tail.append(x)
else:
tail[i] = x
return len(tail)
なぜ tail を直接使用して LIS 列を得ることができないのか？
tail は LIS 自体ではなく、「複数の潜在的な LIS の貪欲な圧縮」であり、常に上書きされ置き換えられるため、完全な経路を保持しません。
例を挙げると：
A = [3, 10, 2, 1, 20]
# tail は：[1, 10, 20] かもしれません
# しかし LIS は [3, 10, 20] です
DP + 戻りを使って、LIS 列を復元#
考え方：LIS 自体を出力するために、「各位置の前駆体」を追加で記録する必要があります。
- dp [i]: A [i] で終わる最長 LIS の長さを示します。
- pre [i]: A [i] の前の要素のインデックスを示します（経路を戻すために使用）。
- 各位置 i を巡回し、すべての j <i かつ A [j] < A [i] の dp [j] を探し、次のようにします：
dp [j] + 1 > dp [i] の場合、dp [i] = dp [j] + 1 を更新し、pre [i] = j を設定します。
def get_LIS_sequence(A):
n = len(A)
dp = [1] * n
pre = [-1] * n # 経路を戻すために使用
max_len = 1
last_index = 0
for i in range(n):
for j in range(i):
if A[j] < A[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
pre[i] = j
if dp[i] > max_len:
max_len = dp[i]
last_index = i
# 経路を戻す
lis = []
i = last_index
while i != -1:
lis.append(A[i])
i = pre[i]
lis.reverse()
return lis