Longest Increasing Subsequence

リストを順に見て、各要素について採用するか除外するかを決めます。nums[i]を採用できるのは、最後に採用した値より大きい場合だけです。再帰関数longest(i, prev)は、最後に採用した要素のインデックスがprev（まだ何も採用していない場合は-1）のとき、インデックスi以降からさらに何個の要素を追加できるかを答えます。

スキップする場合はlongest(i+1, prev)です。採用できる場合、採用すると1 + longest(i+1, i)になります。答えはこの2つのうち大きい方です。リストの末尾を過ぎると追加できる要素はないため、その場合の結果は0です。すべての増加部分列は、採用とスキップの選択からなる1つの経路なので、この探索で最良のものを見逃すことはありません。

値が増加している間は、両方の分岐を探索し続けるため、処理が遅くなります。1, 2, 3, ..., nのようなリストでは、要素を1つ処理するたびに呼び出し回数が2倍になります。2の40乗はすでに約10^12回の呼び出しであり、大きなテストケースでは要素数が2500あります。しかし、longest(i, prev)は組(i, prev)だけに依存するため、異なる問いは最大でもn²個です。それぞれの問いを1回だけ解くのが、次の方法です。

状態。 ending[i]を、最後の要素がnums[i]である最長増加部分列の長さとします。最後の要素を固定すると問題をきれいに分割できます。部分列がどこで終わるかが分かれば、その後に続く可能性のある値が分かるからです。

漸化式。 nums[i]で終わる部分列が複数の要素を持つ場合、nums[i]の直前の要素は、j < iかつnums[j] < nums[i]を満たすあるnums[j]であり、そこまでの部分はできるだけ長いものにする必要があります。したがって、該当するjについてending[i] = 1 + max(ending[j])となります。基本ケース: どの要素も単独で部分列になるため、ending[i]は1から始まります。順序: ending[i]が参照するのはより小さいインデックスだけなので、左から右へ埋めていきます。

[3, 1, 8, 2, 5, 9, 4, 7]の場合、表は[1, 1, 2, 2, 3, 4, 3, 4]となります。たとえば5の前には3、1、または2が続くことができ、そのうち最良なのはending = 2の2なので、ending[4] = 3です。答えは最後の値ではなく、最大の値である4です。最良の部分列はどこで終わってもよいためです。

各インデックスは、それより前のすべてのインデックスを1回ずつ調べるため、処理量はn(n-1)/2回の比較となり、n = 2500の場合は約3.1 × 10^6です。

上の表では、各インデックスにつき1つの長さを記録します。もっと少ない情報だけを記録することもできます。各長さについて、その長さの増加部分列が末尾に取れる値のうち最小のものだけを記録します。長さ k+1 に対して、これを tails[k] と呼びます。末尾の値は小さいほど常に有利です。末尾が9の部分列の後に続けられる値なら、末尾が5の部分列の後にも続けられるからです。

tails は常に厳密な昇順に並んでいます。末尾が t の長さ k+2 の部分列には、末尾が t より小さい長さ k+1 の部分列が含まれるからです。そこで、新しい値 x ごとに、≥ x となる最初の末尾を二分探索します。該当するものがなければ、x はすべての末尾より大きく、最長の部分列を伸ばすので、末尾に追加します。該当するものがあれば、その末尾を x に置き換えます。1つ短い部分列の末尾は x より小さいため、x を追加すると、末尾の値がより小さい同じ長さの部分列が得られます。

[3, 1, 8, 2, 5, 9, 4, 7] の場合、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 自体は部分列ではありません。意味があるのはその長さだけです。この方法はペイシェンスソートとも呼ばれます。各末尾が山札の一番上のカードにあたるカードゲームに由来します。

各要素について、最大で n 個の末尾を対象に二分探索を1回行います。最大の入力では、およそ 2500 × 12 = 30,000 回の処理です。