0
アルゴリズムが正しいかどうかチェックします。省略すべて空白でn文字の文字列、空白文字を省略した文字列をO（n^2）に再構成します
Ex: "itwasthebestoftimes"
は、文字列は単語の有効なシーケンスに分割することが可能かどうかを判断し、動的プログラミングアルゴリズムを与える、として有効な文字列を再構築考える
空白は、O（n ）です。
私の考え：
最初に列のすべてのサブストリングを見つける（O（N ））、及び各サブマップ間隔と空間との長さのその位置のために。
Ex: "it was the best"
[] [-] [-] [--]
[---] []
[]
（見やすくするためにスペースが追加されています）。
上記の例では、「それ」が有効であると2の間隔値を取得し、文字列「TWAS」等、3を取得した「」も有効であり、そして4
の値を取得しますこれは、その後、ミニ・マックス問題に縮小され、インターバルのセットにおいて最大の非オーバーラップ長を見つける。有効な文字列にはすべての文字が含まれている必要があるため、重複しない最大の長さが答えになり、これを見つけるにはTheta（n * log（n））が必要です。
は、したがってソリューションは、Oがかかります（nは + N *ログ（N））= O（nは）
は、私の考えが正しいですか？
ない場合にのみ、どのようにどの行に行くどのサブ選ぶのですか？重複するため新しい部分文字列を下の行に配置しようとすると、既存の部分文字列を列に並べ替えることで、どこかに新しい部分文字列に収まるようになるでしょうか？ – avysk
それを残念に編集しました。サブストリングがどの「行」に入るかは関係ありません。ミニマックスソルバの場合は任意です。重要なことは、間隔の座標によって与えられる衝突があるかどうかを調べることです。行は視覚的表現を簡単にするためにしかありません – mrybak3
実際には、最大長の間隔の互いに素なサブセットを見つけるためのO（n log n）アルゴリズムへのポインタがありますか？ O（n^2）で（同じダイナミックプログラミングで）行うのは簡単ですが、O（n log n）でこれを行う方法はすぐにわかりません。この問題を、最大* number *の長さではなく、不連続な区間の最大数*を見つけることと混同していないと確信していますか？最大数の欲張りアルゴリズムは、実際にはO（n log n）である。 – avysk