最長増加部分列(LIS)の長さを求める - Qiita

この記事の目的 最近、競技プログラミングに手を出し始めました。競プロに関してはほとんどの素人なので難しいことは何もわかりません。そんな状態ですので、さっそくLISの長さを求めるアルゴリズムで躓きました。LISは、競プロをやっている人にとっては常識で、超有名問題らしいのですが、理解するのにだいぶ苦労しました。なので私の理解したことをここに書き留めておきます。 なにぶん競プロ初心者なので、初歩的なこともまだ十分に分かっておらず、説明が長ったらしくなってしまっていますがご容赦ください。なので手っ取り早くコードだけ知りたいという人はほかのサイトをあたるか、一気にページの一番下に進んでください。Python3での実装を示しています。 どこがわからなかったのか 最初にわからなくなったときに、蟻本やWebでアルゴリズムを調べました。これらに載っているのはほとんど同じ内容で、 数列の長さと対応する長さの数