2011-09-02 11 views
5

私は過去2時間このアルゴリズムを理解しようとしていますが、それを得ることはできません。誰か理解しやすいように説明できますか?各要素について'longest increase subsequence'問題を解決するアルゴリズムを説明してください

function lis_length(a) 
    n := a.length 
    q := new Array(n) 
    for k from 0 to n: 
     max := 0; 
     for j from 0 to k, if a[k] > a[j]: 
      if q[j] > max, then set max = q[j]. 
     q[k] := max + 1; 
    max := 0 
    for i from 0 to n: 
     if q[i] > max, then set max = q[i]. 
    return max; 
+1

鉛筆と紙の上に10要素の配列を持つコードを歩きます。または、関数のドキュメントに戻ってください。 –

+0

^@RaymondChen これはあまり役に立たない。このような提案をする以外に何も投稿しない方が良いでしょう。このサイトの回答品質は低下しますが、これはコミュニティだけでなく、自分自身にも害を及ぼすものです。 – guribe94

答えて

5

最初の(ダブル)ループが終了した後、q[i]は、位置がiで終了する最長増加サブシーケンスの長さです。

だけ0k-1jため、q[j]が既に位置jで終わる最大の増加部分列の長さを含んでいたとし、二重のループがどのように動作するか確認します。これを考えると、q[k]はどのように計算されますか?

さて、あなたは1を追加し、最大だった、とq[k]にその値を隠しておく対応q[j]値のかを確認、j < ka[j] < a[k]jのすべてを見つけるだろう。これはまさに内側のループがすることです。

したがって、内部ループのエントリでは、q[j]はすでに0k-1の間のjの正しい値を持っています。終了時には、kにも正しい値が設定されています。だからダブルループが終了するまでに、q[i]はと0nの間のすべての正しい値を持っています。

最後のループは、そのうちの最大のループを選択するだけです。これが答えです。

2

その最大値が現在の要素の値よりも小さくなるように、現在の要素に先行する要素の最長のサブシーケンスの長さだけインクリメントされる現在の要素で作られた要素の最長のサブシーケンスの数を設定します。

アルゴリズムは正の数の配列をとります(要素としてゼロ以下を持つことはできません)。

関連する問題