動的計画法から最適解への転換

最長増加部分列(LIS)問題では、無秩序な配列から厳密に増加する最長の部分列を見つける。例えば配列[10,9,2,5,3,7,101,18]では、LISは[2,3,7,101]で長さ4となる。

動的計画法の基本アプローチ

基本解法は動的計画法(DP)によるO(n²)の実装：

def lis_length_dp(nums):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if nums else 0

この方法は大規模データ（例：10^5要素）では非効率。内ループの最大値探索がボトルネックとなる。

貪欲法による最適化

核心となる洞察：末尾が小さい増加列ほど成長の可能性が高い。例として長さ3の二つの列：

• 列A: [1,3,5]
• 列B: [1,2,4]

後続の値6は両方に追加可能だが、値3は列Bのみ追加可能。これに基づき、配列tailsを管理：

• tails[i] = 長さi+1のLISの最小末尾値
• 数学的証明によりtailsは厳密増加

二分探索を用いた実装

アルゴリズム手順：

1. tails配列を空で初期化
2. 各要素numを走査：
   • numがtails末尾より大：末尾に追加
   • それ以外：num以上の最初の位置を二分探索で検索・置換
3. tailsの長さがLIS長

import bisect

def lis_length_optimized(nums):
    tails = []
    for num in nums:
        if not tails or num > tails[-1]:
            tails.append(num)
        else:
            pos = bisect.bisect_left(tails, num)
            tails[pos] = num
    return len(tails)

計算量: O(nlogn)（n要素の走査＋各lognの二分探索）

動作例と注意点

注意事項:

• tailsはLISそのものではない（末尾値の記録のみ）
• 非厳密増加の場合：bisect_left→bisect_rightに変更
• 境界条件：空配列は0、全要素同値は1を返す

応用事例：ロシアの入れ子人形問題

LeetCode問題354の解法（envelope = [幅, 高さ]）：

def max_envelopes(envs):
    envs.sort(key=lambda x: (x[0], -x[1]))
    tails = []
    for _, h in envs:
        pos = bisect.bisect_left(tails, h)
        if pos == len(tails):
            tails.append(h)
        else:
            tails[pos] = h
    return len(tails)

拡張実装と最適化

二分探索の手動実装例：

def lis_length_manual(nums):
    tails = []
    for num in nums:
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        if left == len(tails):
            tails.append(num)
        else:
            tails[left] = num
    return len(tails)