Longest Increasing Subsequence
整数のリスト nums が与えられます。部分列は、要素の一部を元の順序のまま残し、残りを取り除いたものです。残す要素は隣り合っている必要はありません。左から右へ値が厳密に増加する最長の部分列の長さを返してください。同じ値が連続していても、増加とはみなしません。
関数
- numsinteger-array
- 選択する整数のリスト
- 戻り値integer
- 最長の狭義単調増加部分列の長さ
制約
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
例
- 入力
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- 出力
- 4
- 説明
- 1, 2, 5, 9 は増加し、1, 2, 5, 7 と 1, 2, 4, 7 も同様です。長さは4です。5つの値を選んでも増加し続けるものはありません。
- 入力
- nums = [7, 7, 7, 7]
- 出力
- 1
- 説明
- 値は厳密に増加しなければならないため、同じ部分列に7を2つ含めることはできません。要素が1つだけのものも数えるので、答えは1です。
- 入力
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- 出力
- 4
- 説明
- -4, 0, 3, 16 の長さは 4 です。最初の要素である 12 から始めると、12, 25 のように値は 2 つしか得られません。最良の部分列は先頭から始まる必要はありません。
発展問題
最長増加部分列の長さに加えて、その部分列自体も1つ返し、なおかつ O(n log n) 時間で実行できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
リスト全体で最良の部分列を直接説明するのは困難です。各インデックス
iについて、より限定された質問をしてみましょう。nums[i]でちょうど終わる最長増加部分列は何でしょうか？nums[i]で終わる部分列は、nums[i]だけで構成されるか、以前のあるnums[j] < nums[i]で終わる最良の部分列を続けたものです。そのようなjの中で最良のものを選び、1を加えます。答えは、どこで終わるかにかかわらず、これらの値の最大値です。O(n²)より低い計算量にするには、各長さについて、その長さの部分列が末尾に持ちうる最小の値だけを保持します。これらの値は常にソートされているため、二分探索を使えば、新しい数値が最長の部分列を伸ばすのか、あるいは末尾の値を置き換えるのかを判定できます。
解説
n 個の数値のリストには 2^n 個の部分列があり、すべてを調べるには多すぎます。各インデックスについて、ちょうどその位置で終わる最長増加部分列の長さを求めると、O(n²) の表になります。最速の方法では、各長さについて、その長さの部分列が末尾に持つことのできる最小値を保持し、二分探索で各要素の位置を決めます。
各要素を選択するか、スキップする
正しいが、最大のテストでは終わらない
考え方
各要素について採用するかどうかを決めます。nums[i]を採用できるのは、最後に採用した値より大きい場合だけです。longest(i, prev)は、最後に採用した要素がprev（または-1）にあるとき、インデックスi以降から追加できる要素の最大数です。スキップするとlongest(i+1, prev)、採用すると1 + longest(i+1, i)になります。すべての増加部分列は、これらの選択による経路の1つです。
1, 2, 3, ..., nでは両方の分岐が開いたままとなり、要素が1つ増えるごとに呼び出し数が倍になります。2^40はすでに約10^12です。一方、異なる組(i, prev)は最大でもn²個です。
アルゴリズム
prevが最後に残した要素のインデックス（または-1）であるとき、longest(i, prev)を書きます。iが末尾を過ぎていたら、0 を返します。nums[i]をスキップします:best = longest(i+1, prev)。prevが-1であるか、nums[i] > nums[prev]の場合は、それを残します:best = max(best, 1 + longest(i+1, i))。bestを返します。答えはlongest(0, -1)です。
def lengthOfLIS(nums):
def longest(i, prev):
# The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
# prev is -1 while nothing has been taken.
if i == len(nums):
return 0
best = longest(i + 1, prev) # skip nums[i]
if prev == -1 or nums[i] > nums[prev]:
best = max(best, 1 + longest(i + 1, i)) # take nums[i]
return best
return longest(0, -1)各インデックスで終わる最長の部分列
考え方
ending[i]を、最後の要素がnums[i]である最長増加部分列の長さとします。nums[i]の前の要素は、存在する場合、j < iかつnums[j] < nums[i]を満たすnums[j]であり、そこまでの部分はできるだけ長くします。したがって、そのようなjについてending[i] = 1 + max(ending[j])となり、該当するものがなければ1です。左から右へ埋めていきます。
[3, 1, 8, 2, 5, 9, 4, 7]の場合、表は[1, 1, 2, 2, 3, 4, 3, 4]です。5の前には3、1、2のいずれも置くことができ、そのうち最長のものの長さは2なので、ending[4] = 3です。最良の部分列はどこで終わってもよいため、答えは最も大きい値です。
n(n-1)/2回の比較：n = 2500の場合、約3.1 × 10^6回です。
アルゴリズム
- すべての要素を1に設定して、
endingを作成します。 - 左から右へ各
iについて、すべてのj < iを確認します。 nums[j] < nums[i]の場合、値がより大きくなるならending[i]をending[j] + 1に設定します。ending内の最大値を返します。
def lengthOfLIS(nums):
n = len(nums)
# ending[i]: the longest increasing subsequence that ends with nums[i]
ending = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
ending[i] = ending[j] + 1
return max(ending)二分探索による最小の末尾
考え方
各長さについて、その長さの増加部分列が終わり得る最小の値だけを保持します。長さ k+1 に対する値は tails[k] です。終端の値が小さいほうが不利になることはありません。9 の後に続けられるものは、5 の後にも続けられるからです。tails は常に狭義単調増加になります。長さ k+2 の増加部分列の最後の値を取り除くと、それより小さい値で終わる長さ k+1 の部分列が得られるからです。
各 x について、≥ x を満たす最初の tail を二分探索します。そのような値がなければ、x を追加します。これで最長の部分列が伸びます。そうでなければ、その tail を x に置き換えます。1 つ短い部分列は x より小さい値で終わるため、x に置き換えることで、終端の値を小さくしつつ同じ長さを保てます。
例 1 では、tails は [3]、[1]、[1, 8]、[1, 2]、[1, 2, 5]、[1, 2, 5, 9]、[1, 2, 4, 9]、[1, 2, 4, 7] と変化します。長さは 4 です。[1, 2, 4, 9] では 4 が 9 の後に現れているため、意味を持つのは tails の長さだけです。
アルゴリズム
- 空のリスト
tailsから始めます。 numsの各xについて、tails[k] ≥ xを満たす最初のインデックスkを二分探索します。≥ xを満たす末尾要素がなければ、xを追加します。- それ以外の場合は、
tails[k] = xと設定します。 tailsの長さを返します。
from bisect import bisect_left
def lengthOfLIS(nums):
# tails[k]: the smallest last value of any increasing subsequence of length k + 1
tails = []
for x in nums:
k = bisect_left(tails, x) # the first tail that is >= x
if k == len(tails):
tails.append(x) # x extends the longest subsequence so far
else:
tails[k] = x # x is a smaller ending for length k + 1
return len(tails)
落とし穴と境界ケース
- 最大の要素ではなく、
ending[n-1]を返してしまう。[1, 2, 3, 0]の場合、最後の要素は1だが、答えは3。 <ではなく≤で比較してしまう。[7, 7, 7, 7]は4ではなく1を返す必要がある。- tails版で、最初の末尾として
≥ xではなく> xを検索してしまう。すると2つ目の7が1つ目の後に追加され、等しい値も増加として数えられる。 - 誤って連続部分列の問題を解いてしまう。例1で隣り合う要素の最長増加列は2, 5, 9（長さ3）だが、答えは4。
- 配列のインデックスが1から始まるLuaやRで、0始まりのインデックスを使い続けてしまう。
prev = -1のマーカーは0になり、二分探索はインデックス1から現在のサイズまでを対象にする。
よくある質問3
最長増加部分列の時間計算量はどれくらいですか？
tails メソッドは、要素ごとに二分探索を1回行うため、時間計算量は O(n log n)、空間計算量は O(n) です。すべてのインデックスのペアに対する表は時間計算量が O(n²) で、すべての部分列を試す方法は O(2ⁿ) です。
最長増加部分列における忍耐ソートとは何ですか？
これはカードゲームにちなんで名付けられた、テールズ法です。それぞれのテールは山札の一番上のカードを表します。カードは、その値以上のカードが一番上にある最も左の山札に置くか、新しい山札を作ります。山札の数が答えです。
代わりに、最長非減少部分列はどのように求めますか？
隣接する値が等しいことを許容します。表では、nums[j] ≤ nums[i]を使います。tails法では、xより厳密に大きい最初の末尾を探します。これにより、等しい値は末尾を置き換えるのではなく、リストを延長します。[7, 7, 7, 7]は4を返します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def lengthOfLIS(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [3, 1, 8, 2, 5, 9, 4, 7]
期待される出力
4