6

私はうまく機能する次のアルゴリズムを持っています

ここで自分で説明しようとしましたhttp://nemo.la/?p=943そしてここで説明されています http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/同様に、スタックオーバーフローでも

最長の非単調増加サブシーケンスを生成するように変更したい

シーケンス 30 20 20 10 10 10 10 の場合

答えは 4 である必要があります: "10 10 10 10"

しかし、nlgn バージョンのアルゴリズムでは機能しません。最初の要素「30」を含むように s を初期化し、2 番目の要素 = 20 から開始します。次のようになります。

  1. 最初のステップ: 30 は 20 以下です。20 より大きい最小の要素を見つけます。新しい s は「20」になります。

  2. 2 番目のステップ: 20 は 20 以上です。シーケンスを拡張すると、s には "20 20" が含まれます。

  3. 3 番目のステップ: 10 は 20 以下です。「20」である 10 より大きい最小の要素を見つけます。新しい s は「10 20」になります

その後、s は決して大きくならず、アルゴリズムは 4 ではなく 2 を返します。

int height[100];
int s[100];

int binary_search(int first, int last, int x) {

    int mid;

    while (first < last) {

        mid = (first + last) / 2;

        if (height[s[mid]] == x)
            return mid;

        else if (height[s[mid]] >= x)
            last =  mid;

        else
            first = mid + 1;
    }
    return first; /* or last */
}

int longest_increasing_subsequence_nlgn(int n) {

    int i, k, index;

    memset(s, 0, sizeof(s));

    index = 1;
    s[1] = 0; /* s[i] = 0 is the index of the element that ends an increasing sequence of length  i = 1 */

    for (i = 1; i < n; i++) {

        if (height[i] >= height[s[index]]) { /* larger element, extend the sequence */

            index++; /* increase the length of my subsequence */
            s[index] = i; /* the current doll ends my subsequence */

        }
        /* else find the smallest element in s >= a[i], basically insert a[i] in s such that s stays sorted */
        else {
            k = binary_search(1, index, height[i]);

            if (height[s[k]] >= height[i]) { /* if truly >= greater */
                s[k] = i;
            }
        }
    }
    return index;
}
4

6 に答える 6

5

関数の問題を除いて、コードはほぼ機能しますbinary_search()。この関数は、最長の非減少シーケンスが必要なため、ターゲット要素(x)よりも大きい最初の要素のインデックスを返す必要があります。これに変更すればOKです。

C++ を使用するstd::lower_bound()とstd::upper_bound()、この紛らわしい問題を解決するのに役立ちます。ちなみにif文" if (height[s[k]] >= height[i])"は不要です。

int binary_search(int first, int last, int x) {

    while(last > first)
    {
        int mid = first + (last - first) / 2;
        if(height[s[mid]] > x)
            last = mid;
        else
            first = mid + 1;
    }

    return first; /* or last */
}
于 2014-02-12T03:31:57.887 に答える
5

厳密に増加していない最長のサブシーケンスを見つけるには、次の条件を変更します。

  1. アクティブ リストのすべての終了候補の中で が最小の場合A[i]、長さ の新しいアクティブ リストを開始します1。
  2. アクティブ リストのすべての最終候補の中で が最大の場合A[i]、最大のアクティブ リストを複製し、 だけ拡張しA[i]ます。
  3. が間にある場合A[i]、 より小さい最大の終了要素を持つリストが見つかりますA[i]。このリストを複製して拡張しA[i]ます。この変更されたリストと同じ長さの他のすべてのリストを破棄します。

に：

  1. A[i]がアクティブ リストのすべての終了候補の最小値よりも小さい場合、長さ の新しいアクティブ リストを開始します1。
  2. アクティブ リストのすべての最終候補の中で が最大の場合A[i]、最大のアクティブ リストを複製し、 だけ拡張しA[i]ます。
  3. が間にある場合、より小さいか等しいA[i]最大の終了要素を持つリストが見つかります。このリストを複製して拡張します。この変更されたリストと同じ長さの他のすべてのリストを破棄します。 A[i]A[i]

サンプル シーケンスの 4 番目のステップは次のようになります。

1010は(最小要素)より小さくありません。以下の最大の要素を見つけます10(つまり になりますs[0]==10)。このリストを複製して拡張し10ます。長さ 2 の既存のリストを破棄します。新しいリストは にsなり{10 10}ます。

于 2014-02-12T01:15:10.873 に答える
4

辞書式比較を使用して、最長増加サブシーケンス アルゴリズムを順序付きペア (A[i], i) に適用するだけです。

于 2014-02-12T04:21:24.887 に答える