38

数列が与えられ、与えられた入力から最長増加部分列を見つける必要があります（連続である必要はありません）。

これへのリンク（ウィキペディアで最も長く増加しているサブシーケンス）を見つけましたが、さらに説明が必要です。

誰かがO（n log n）の実装を理解するのを手伝ってくれるなら、それは本当に役に立ちます。例を挙げてアルゴを説明できれば、それは本当にありがたいことです。

私は他の投稿も見ましたが、私が理解していなかったのは次のとおりです。i = 1、2、...nの場合はL= 0：X [M[j]]<Xとなる最大の正のj≤Lの二分探索[i]（またはそのような値が存在しない場合はj = 0に設定）上記のステートメント、どこから二分探索を開始しますか？M []、X []を初期化する方法は？

4

7 に答える 7

99

より単純な問題は、最も長く増加するサブシーケンスの長さを見つけることです。最初にその問題を理解することに集中できます。アルゴリズムの唯一の違いは、 P配列を使用しないことです。

xはシーケンスの入力であるため、次のように初期化できます: x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

mは、これまでに見つかった各長さの最良のサブシーケンスを追跡します。最適なのは、最小の終了値を持つものです (より広い範囲の値をその後に追加できます)。長さと終了値は、各サブシーケンスに保存する必要がある唯一のデータです。

mの各要素はサブシーケンスを表します。m[j]の場合、

  • jはサブシーケンスの長さです。
  • m[j]は、サブシーケンスの最後の要素のインデックス ( x内) です。
  • したがって、x[m[j]]はサブシーケンスの最後の要素の値です。

Lは、これまでに見つかった最長のサブシーケンスの長さです。mの最初のL個の値は有効で、残りは初期化されていません。mは、最初の要素が 0 で、残りが初期化されていない状態で開始できます。アルゴリズムが実行されるとLが増加し、mの初期化された値の数も増加します。

実行例を次に示します。x[i]、および各反復の最後にmが与えられます (ただし、インデックスの代わりにシーケンスの値が使用されます)。

各反復での検索は、 x[i]を配置する場所を探しています。可能な限り右にある必要があり (最長のシーケンスを取得するため)、左側の値よりも大きくなければなりません (つまり、増加するシーケンスです)。

 0:  m = [0, 0]        - ([0] is a subsequence of length 1.)
 8:  m = [0, 0, 8]     - (8 can be added after [0] to get a sequence of length 2.)
 4:  m = [0, 0, 4]     - (4 is better than 8. This can be added after [0] instead.)
 12: m = [0, 0, 4, 12] - (12 can be added after [...4])
 2:  m = [0, 0, 2, 12] - (2 can be added after [0] instead of 4.)
 10: m = [0, 0, 2, 10]
 6:  m = [0, 0, 2, 6]
 14: m = [0, 0, 2, 6, 14]
 1:  m = [0, 0, 1, 6, 14]
 9:  m = [0, 0, 1, 6, 9]
 5:  m = [0, 0, 1, 5, 9]
 13: m = [0, 0, 1, 5, 9, 13]
 3:  m = [0, 0, 1, 3, 9, 13]
 11: m = [0, 0, 1, 3, 9, 11]
 7:  m = [0, 0, 1, 3, 7, 11]
 15: m = [0, 0, 1, 3, 7, 11, 15]

これで、長さが 6 で末尾が 15 のサブシーケンスがあることがわかりました。サブシーケンスの実際の値は、ループ中にP配列に格納することで見つけることができます。

最良のサブシーケンスを取得する:

Pは、各数値について、最長のサブシーケンス (x のインデックスとして) の前の要素を格納し、アルゴリズムが進むにつれて更新されます。たとえば、8 を処理するとき、それが 0 の後に来ることがわかっているので、8 が 0 の後にあるという事実をPに格納します。リンクされたリストのように最後の番号から逆方向に作業して、シーケンス全体を取得できます。

したがって、各番号について、その前にある番号がわかります。7 で終わる部分列を見つけるために、Pを見て、次のことを確認します。

7 is after 3
3 is after 1
1 is after 0

したがって、サブシーケンス [0, 1, 3, 7] があります。

7 または 15 で終わるサブシーケンスは、いくつかの番号を共有します。

15 is after 11
11 is after 9
9 is after 6
6 is after 2
2 is after 0

したがって、サブシーケンス [0, 2, 6, 9, 11] と [0, 2, 6, 9, 11, 15] (最も長く増加するサブシーケンス) があります。

于 2011-02-11T21:06:46.897 に答える
1

FJBの回答、Java実装に基づく：

public class Lis {

private static int[] findLis(int[] arr) {
    int[] is = new int[arr.length];
    int index = 0;
    is[0] = index;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[is[index]]) {
            for (int j = 0; j <= index; j++) {
                if (arr[i] < arr[is[j]]) {
                    is[j] = i;
                    break;
                }
            }
        } else if (arr[i] == arr[is[index]]) {

        } else {
            is[++index] = i;
        }
    }

    int[] lis = new int[index + 1];
    lis[index] = arr[is[index]];

    for (int i = index - 1; i >= 0; i--) {
        if (is[i] < is[i + 1]) {
            lis[i] = arr[is[i]];
        } else {
            for (int j = is[i + 1] - 1; j >= 0; j--) {
                if (arr[j] > arr[is[i]] && arr[j] < arr[is[i + 1]]) {
                    lis[i] = arr[j];
                    is[i] = j;
                    break;
                }
            }
        }
    }

    return lis;
}

public static void main(String[] args) {
    int[] arr = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11,
            7, 15 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();

    arr = new int[] { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();
}

}

于 2012-05-02T21:38:52.210 に答える