シーケンスを非減少シーケンスを形成できる部分に分割するためのカットの最小数

Question

私はN個の整数、例えば3,1,4,5,2,8,7を持っています。重複があるかもしれません。私は、このシーケンスを非連続シーケンスから形成できるように、このシーケンスを連続したサブシーケンスに分割したいと考えています。カットの最小数を計算するには？上記の例では、このシーケンスを{3}、{1}、{4,5}、{2}、{7}、{8}に分割して{1,2} 、3、4、5、7、8}。これを行う最速の方法は何ですか？

誰かがいくつかの数字が等しいと仮定して解決する方法を知っていますか？

Answer 1

私は、値が減少するポイントで非減少セグメントにカットし、これらのセグメントを（単一の）マージフェーズへの入力として使用します - ソートマージの場合と同じセグメントで可能であれば、ネクタイの場合。あるセグメントから別のセグメントに切り替える必要がある場合に、カットの追加の場所を作成します。

出力はソートされているため、ジョブを実行するのに十分なカットが生成されます。カットが生成されるポイント、または元のシーケンスが別の場所にある数にジャンプするため、ギャップを作成する必要があるポイントでカットが生成されるため、これらのカットをすべて含まないシーケンスはソート順に並べ替えることができません。

マージオーバーヘッドの最悪のケースは、初期シーケンスが減少している場合です。ヒープを使用して次に選択するシーケンスを追跡すると、これはコストn log nのヒープソートに変わります。同じ値のすべての出現をヒープから引っ張って、何をすべきかを決めることによって、ネクタイを処理します。

Answer 2

この方法は、リストに重複が含まれていない場合に有効です。おそらくそれらは最初に効率的に世話をすることができます。

フェンウィックツリーを使用して、O(n * log n)時間とO(n)時間の順列反転ベクトルを計算することができます。同じ番号のベクトルの連続したセグメントは、切断する必要がないセクションを表すことができます。残念ながら、彼らはまた、

6と 3がシーケンスのカット、 [1,4,5,7]を意味するものではあり

Array: {8,1,4,5,7,6,3} 
Vector: 0,1,1,1,1,2,5 

、同様に、偽陽性を返すことができます。これに対処するため、各要素に続く小さな要素の数を表す2番目の逆ベクトルを取ります。両方のベクトルで平行な連続したセグメントを切り取る必要はありません。

Array: {8,1,4,5,7,6,3,0} 
Vector: 0,1,1,1,1,2,5,7 // # larger preceding 
Vector: 7,1,2,2,3,2,1,0 // # smaller following 
      |---| // not cut 

Array: {3,1,4,5,2,8,7} 
Vectors: 0,1,0,0,3,0,1 
      2,0,1,1,0,1,0 
      |---| // not cut 

Array: {3,1,2,4} 
Vectors: 0,1,1,0 
      2,0,0,0 
      |---| // not cut