4

array が与えられた場合、交互に増加する値と減少する値を使用して、最長のサブシーケンスの長さを見つける必要があります。

たとえば、配列が の場合 7 4 8 9 3 5 2 1、L = 6for7,4,8,3,5,2または7,4,9,3,5,1など。

また、最初に小さな要素があり、次に大きな要素がある場合もあります。

これに対する最も効率的な解決策は何ですか? 私はDPソリューションを念頭に置いていました。そして、ブルートフォースを使用してそれを行うとしたら、どうすれば (O(n^3) ?) ?

そしてそれは宿題の問題ではありません。

4

1 に答える 1

14

ここでは実際に動的計画法のアプローチを使用できます。簡単にするために、そのようなシーケンスseqの最大長のみを見つける必要があると仮定します(シーケンス自体を見つけるためにソリューションを微調整するのは簡単です)。

各インデックスに対して、2 つの値を格納します。

  • 最後のステップが増加していた要素で終わる交互シーケンスの最大長 ( incr [i] など)
  • 最後のステップが減少していた要素で終わる交互シーケンスの最大長 (たとえば、decr [i])

また、定義により、incr[0] = decr[0] = 1

次に、各 incr[i] を再帰的に見つけることができます。

incr[i] = max(decr[j])+1, where j < i and seq[j] < seq[i]
decr[i] = max(incr[j])+1, where j < i and seq[j] > seq[i]

シーケンスの必要な長さは、両方の配列の最大値になります。このアプローチの複雑さは O(N*N) であり、2N の余分なメモリが必要です (N は最初のシーケンスの長さです)。

c の簡単な例:

int seq[N]; // initial sequence
int incr[N], decr[N];

... // Init sequences, fill incr and decr with 1's as initial values

for (int i = 1; i < N; ++i){
    for (int j = 0; j < i; ++j){
         if (seq[j] < seq[i]) 
         {
             // handle "increasing" step - need to check previous "decreasing" value
             if (decr[j]+1 > incr[i])  incr[i] = decr[j] + 1;
         }
         if (seq[j] > seq[i]) 
         {
             if (incr[j]+1 > decr[i])  decr[i] = incr[j] + 1;
         }
    }
}

... // Now all arrays are filled, iterate over them and find maximum value

アルゴリズムの仕組み:

ステップ 0 (初期値):

seq  = 7   4 8 9 3 5 2 1
incr = 1   1 1 1 1 1 1 1
decr = 1   1 1 1 1 1 1 1

ステップ 1インデックス 1 ('4') の値を取得し、以前の値を確認します。7 > 4 なので、「インデックス 0 からインデックス 1 への減少ステップ」を作成し、新しいシーケンス値:

incr = 1 1   1 1 1 1 1 1
decr = 1 2   1 1 1 1 1 1

ステップ 2.値 8 を取り、前の値を反復します。

7 < 8、増加ステップを作成: incr[2] = MAX(incr[2], decr[0]+1):

incr = 1 1 2   1 1 1 1 1
decr = 1 2 1   1 1 1 1 1

4 < 8、増加ステップを作成: incr[2] = MAX(incr[2], decr[1]+1):

incr = 1 1 3   1 1 1 1 1
decr = 1 2 1   1 1 1 1 1

等...

于 2012-09-17T16:06:12.250 に答える