5

私のコードは現在、最大の部分文字列の長さを返します:

for(int i = 1; i<=l-1;i++)
{
   counter = 1;

   for(int j = 0; j<i;j++)
   {
      if(seq[j]<seq[j+1])
      {
         count[j] = counter++;    
      }
   }
}
     for(int i = 0;i<l-1;i++)
     {
        if(largest < count[i+1])
        {
           largest = count[i+1];
        }

     }

seq がシーケンス内の番号であると仮定します。したがって、シーケンスが 5;3;4;8;6;7 の場合、4 が出力されます。ただし、昇順で最も長く存在する 3;4;6;7 も出力したいと思います。

最大のサブシーケンス自体と実際のシーケンスの長さを取得しようとしていますが、すでに長さがあります.. 私の本能は、カウントを計算しながら、各数値を配列に格納することです。したがって、最長のカウントを返すと、それにアタッチされている配列も返されます。これはハッシュテーブルで実行できると思いますが、それらの使用方法がわかりません。

答えではなく、ヒントを探しているだけです。

ありがとう

4

1 に答える 1

2

最長昇順サブシーケンスの動的計画法アルゴリズムを実装する必要があります。アイデアは、各位置の値のペアを保存することですi:

  • position で終わる最長の昇順サブシーケンスの長さi
  • そのような昇順のサブシーケンスで現在の項目の前にある項目のインデックス、または-1前のすべての番号が現在の番号以上である場合。

{Length=1, Prior=-1}これらの両方の配列は、最初のペアを に設定し、配列を昇順でウォークし、 index で現在のアイテムの「最適な」先行を探すことで簡単に作成できますi。先行者は、次の 2 つの条件に適合する必要があります。

  • iより低いインデックスを持ち、のアイテムよりも小さくなければなりません。
  • これまでに見つけた長さよりも長い昇順のサブシーケンスを終了する必要があります。

シーケンスのデータは次のようになります。

Index:        0  1  2  3  4  5
Value:        5  3  4  8  6  7
------------  ----------------
Length:       1  1  2  3  3  4
Predecessor: -1 -1  1  2  2  4

実行が終了したら、lengths 配列の中から最大値を見つけ、ヒットするまで前任者のインデックスを使用して先頭にチェーンします-1。

于 2013-07-26T16:16:35.157 に答える