最長連続部分列

同じ列を、何度も歩き直している

[100, 4, 200, 1, 3, 2] の中で、連続する整数が一番長く続くのは 1, 2, 3, 4 の 4 個です。並んでいる順は関係ありません。

素直に書くと、各要素から右へ「次の数はあるか」と伸ばしていく形になります。この配列で歩数を数えてみます。1 から 4 歩、2 から 3 歩、3 から 2 歩、4 から 1 歩、100 と 200 から 1 歩ずつ。合わせて 12 歩です。答えは 4 なのに 12 歩かかりました。

長さ L の列があると、そこだけで L * (L + 1) / 2 歩です。1000 個が 1 本に繋がっていたら、答えを出すのに 50 万歩かかります。

途中から歩き出しても、新しいことは分からない

2 から歩き出して分かるのは「2, 3, 4 で 3 個」ということだけです。これは 1 から歩いたときに、途中で通り過ぎた話です。3 からも 4 からも同じで、列の途中を起点にした探索は、必ず誰かの歩みの一部にしかなりません。

意味があるのは、列の先頭から歩き出したときだけです。では、ある値が列の先頭かどうかは、どう見分けるか。その値より 1 小さい値が、どこにも入っていないときです。

• 1 より 1 小さい 0 は入っていない。だから 1 は先頭
• 2 より 1 小さい 1 は入っている。だから 2 からは歩かない

先頭だけを起点にすれば、各値が触られるのは「先頭かどうかの確認」と「どれかの列の途中として通られるとき」の 2 回だけです。12 歩が 4 歩に戻り、1000 個でも 1000 歩で終わります。

「その値があるか」を一瞬で聞ける入れ物

この作戦は「1 小さい値はあるか」を要素の数だけ聞きます。聞くのが遅ければ、せっかく歩数を減らしても意味がありません。配列に聞くと端から探すので、件数が増えるほど遅くなります。

Set は入れた値をそのまま覚えていて、「あるか」の問いに件数と関係のない速さで答えます。同じ値を 2 回入れても 1 つにまとまるので、重複を含む配列でも数がずれません。

空の配列と、長さの初期値

配列が空なら答えは 0 です。最長の長さを入れる変数を 1 から始めると、1 個も無い配列に 1 を返してしまいます。0 から始めて、列を歩いたときだけ更新してください。

歩いた長さの数え方も、1 つずれやすいところです。先頭の値そのものを 1 個目と数えてから、次の値が見つかるたびに増やします。先頭を数え忘れると、答えが常に 1 少なくなります。

1. set を使って O(n) (期待計算量) で解く
2. 重複や負の数が含まれていても正しく動作すること
3. 空配列の場合は 0 を返す