既存投稿一覧ページへのリンク
最長増加部分列(最長減少部分列)
このデータ構造を知ったときから、株価の上昇下落に適用できると思って、ずっと挑戦してきました。
最長増加部分列って、複数解あって、復元パターン全部をどうやって求めれば良いのかなぁ～と結構考えていたんだけど、普通にAtCoderの問題解いていればC問題レベルの難易度で何度も出ていましたね⋯
つまり、最長増加部分列や最長減少部分列の長さを求め、その数の部分数列を求めればよいだけの話だったと。
もっとスマートな解き方もあるだろうけれど、私が理解出来るレベルに落とし、使えることが重要ということで。
サンプルコード
sample_code.py
def longest_monotonic_subsequence(arr, increasing=True):
if not arr:
return []
n = len(arr)
dp = [1] * n
prev = [-1] * n
max_length = 1
max_index = 0
# 比較演算子を動的に選択
compare = (lambda a, b: a > b) if increasing else (lambda a, b: a < b)
for i in range(1, n):
for j in range(i):
if compare(arr[i], arr[j]) and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
prev[i] = j
if dp[i] > max_length:
max_length = dp[i]
max_index = i
# 部分列の再構築
sequence = []
while max_index != -1:
sequence.append(arr[max_index])
max_index = prev[max_index]
return sequence[::-1]
def find_monotonic_sequences_indices(arr, length, reverse=False):
# 結果を格納するリストを初期化
result = []
# 入力配列の長さを取得
n = len(arr)
# バックトラック法で部分列を探索する内部関数
def backtrack(start, path, reverse):
# 現在のパスが指定長に達した場合、結果に追加
if len(path) == length:
result.append(path.copy()) # コピーを追加（参照の共有を防ぐ）
return
# 現在位置から配列末尾まで探索
for i in range(start, n):
if not reverse: # 増加部分列モード
# 最初の要素 または 現在要素が前要素より大きい場合
if not path or arr[i] > arr[path[-1]]:
path.append(i) # インデックスをパスに追加
backtrack(i + 1, path, reverse) # 次の位置から再帰
path.pop() # バックトラック（状態を戻す）
else: # 減少部分列モード
# 最初の要素 または 現在要素が前要素より小さい場合
if not path or arr[i] < arr[path[-1]]:
path.append(i) # インデックスをパスに追加
backtrack(i + 1, path, reverse) # 次の位置から再帰
path.pop() # バックトラック（状態を戻す）
# バックトラックの開始（初期位置0、空パス）
backtrack(0, [], reverse)
# 最終結果を返却
return result
if __name__=="__main__":
arr = [0, 8, 0, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 15, 7, 15]
# 最長増加部分列
lis = longest_monotonic_subsequence(arr) # LIS: [0, 4, 6, 9, 13, 15]
# 最長増加部分列(総出力)※インデックス番号※
print(find_monotonic_sequences_indices(arr, len(lis)))
# 最長減少部分列
lis_minus = longest_monotonic_subsequence(arr, False) # LDS: [12, 10, 9, 5, 3]
# 最長減少部分列(総出力)※インデックス番号※
print(find_monotonic_sequences_indices(arr, len(lis_minus), True))
出力イメージ
元の数列
最長増加部分列
最長減少部分列
これ、株価チャート眺めたり、ゲームのネタに使えそうなので活用したいものです。