5

過去 2 時間、このアルゴリズムを理解しようとしてきましたが、理解できないようです。誰か分かりやすく説明してくれませんか？

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;
4

2 に答える 2

5

最初の（double）ループが終了した後、q[i]は位置で終了する最長増加部分列の長さですi。

ダブルループがどのように機能するかを確認するためにq[j]、位置で終わる最大の増加部分列の長さがすでに含まれていると仮定しますが、との間jのみです。これを考えると、どのように計算しますか？j0k-1q[k]

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

したがって、内側のループに入るときに、とq[j]の間のjの正しい値がすでにあり0ますk-1。また、終了時に、の正しい値もありますk。したがって、二重ループが終了するまでに、との間q[i]のすべてに対して正しい値があります。i0n

最後のループは、それらの中で最大のものを選択するだけで、それが答えです。

于 2011-09-02T14:45:25.943 に答える
2

各要素に対して、現在の要素で作成された要素の最長サブシーケンスのカウントを、現在の要素の前にある要素の最長サブシーケンスの 1 つの長さだけインクリメントして、それらの最大値が現在の要素の値よりも小さくなるように設定します。

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

于 2011-09-02T14:28:15.600 に答える