最長の二峰性サブシーケンスを見つけるための JavaScript プログラム | DP-15

動的プログラミングを使用して、各配列内の最長のビットニック シーケンスを見つけます。モノクロ シーケンスは、最初に増加し、次に減少するシーケンスです。最長のモノクロ シーケンスを見つけるには、2 段階のアプローチを使用します。まず、指定された配列内で最長の増加するサブシーケンスを見つけてから、指定された配列の逆の順序で最長の減少するサブシーケンスを見つけます。最後に、2 つのサブシーケンスの長さを加算し、1 を減算して、中間の共通要素を除外します。

＃＃＃方法＃＃＃

ビットニック シーケンスは、最初に増加し、次に減少するシーケンスです。指定された配列内で最長のモノクロ シーケンスを見つける方法は、動的プログラミングを使用することです。

各インデックスで終わる最長の増加するサブシーケンスの長さを格納するために使用される 2 つの配列「inc」と「dec」を初期化します。
配列をループし、前のインデックスの値を使用して各インデックスの「inc」と「dec」の値を更新します。
各インデックスで「inc」と「dec」の合計から 1 を引いた最大値を見つけます。これにより、そのインデックスを含む最長のビット増加サブシーケンスの長さがわかります。
ステップ 3 で見つかった最大値を、最長のビット増加サブシーケンスの長さとして返します。
最長のモノクロ シーケンスを再構築するには、「inc」と「dec」の値を使用して、ステップ 3 で最大値を与えたインデックスから開始してバックトラックします。
再構築されたシーケンスを最長のモノクロ シーケンスとして返します。
Example

の中国語訳は次のとおりです:

Example

これは、動的プログラミングを使用して最長のビットニック サブシーケンスを見つける JavaScript プログラムの完全な動作例です −

リーリー

説明

の中国語訳は次のとおりです:

説明

最初のステップは、入力配列
• arr

  と同じ長さの 2 つの配列 lis と lds を初期化し、1 を入力することです。 。 lis は「最長の増加部分列」を表し、lds は「最長の減少部分列」を表します。

次のステップでは、
• lis[i]

  を計算します。これは、arr[i] で終わる最長の増加サブシーケンスの長さです。これは、j が 0 から i-1 の範囲にある入れ子になったループによって実現されます。 arr[i] > arr[j] の場合、 lis[i] を現在の値の最大値と lis[j] 1 に更新します。

次のステップでは、
• lds[i]

  を計算します。これは、arr[i] から始まる最長の降順サブシーケンスの長さです。これは、j が n-1 から i 1 までの範囲にある入れ子のループによって行われます。 arr[i] > arr[j] の場合、lds[i] を現在の値と lds[j] の最大値 1 に更新します。 。

最後に、入力配列の
• n

  要素をループして、lis[i] lds[i] - 1 の最大値を見つけます。これは # を意味します。 ##arr[i] は、終了点と開始点の最長のビット シーケンスの長さです。この値は変数 maxLength に保存されます。

  この関数は、入力配列内の最も長いビット増加サブシーケンスの長さである
maxLength
• を返します。

以上が最長の二峰性サブシーケンスを見つけるための JavaScript プログラム | DP-15の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。