既存投稿一覧ページへのリンク

一覧ページ

最長増加部分列(最長減少部分列)

このデータ構造を知ったときから、株価の上昇下落に適用できると思って、ずっと挑戦してきました。
最長増加部分列って、複数解あって、復元パターン全部をどうやって求めれば良いのかなぁ～と結構考えていたんだけど、普通に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))

出力イメージ

元の数列

最長増加部分列

最長減少部分列

これ、株価チャート眺めたり、ゲームのネタに使えそうなので活用したいものです。