0

O（n log n）時間で配列の各位置から始まる最長増加部分列をどのように見つけることができますか？配列の各位置で終わる最長増加配列を見つける手法を見てきましたが、他の方法を見つけることができません円形。

たとえば、シーケンス「3 2 4 4 3 2 3」の場合、出力は「2 2 1 1 121」でなければなりません。

4

2 に答える 2

1

私は簡単で汚い JavaScript 実装を作成しました (注: O(n^2) です):

function lis(a) {
    var tmpArr = Array(),
        result = Array(),
        i = a.length;

    while (i--) {
        var theValue = a[i],
            longestFound = tmpArr[theValue] || 1;

        for (var j=theValue+1; j<tmpArr.length; j++) {
            if (tmpArr[j] >= longestFound) {
                longestFound = tmpArr[j]+1;
            }
        }
        result[i] = tmpArr[theValue] = longestFound;
    }
    return result;
}

jsFiddle: http://jsfiddle.net/Bwj9s/1/

配列を右から左に実行し、前の計算を後続の検索用に別の一時配列に保持します。

にはtmpArray、指定された値で始まる以前に見つかったサブシーケンスが含まれているため、 value でtmpArray[n]始まる (現在の位置の右側にある) 見つかった最長のサブシーケンスを表しますn。

ループは次のようになります: すべてのインデックスについて、値 (およびそれ以上のすべての値) を検索して、値をtmpArray前に追加できるサブシーケンスが既に見つかっているかどうかを確認します。見つかった場合は、その長さに 1 を追加tmpArrayし、値を更新して、次のインデックスに移動します。機能する (より高い) サブシーケンスが見つからない場合は、tmpArrayfor の値を 1 に設定して先に進みます。

O(n log n) にするために、tmpArrayは常に減少する配列になることがわかります。部分的なループではなく、二分探索を使用できますし、使用する必要があります。

于 2012-10-18T07:38:50.570 に答える
0

編集：投稿を完全に読んでいませんでした。申し訳ありません。すべてのシーケンスで最長の増加サブシーケンスが必要だと思いました。動作するようにコードを再編集しました。

実際、線形時間でそれを行うことは可能だと思います。次のコードを検討してください。

int a[10] = {4, 2, 6, 10, 5, 3, 7, 5, 4, 10};
int maxLength[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; // array of zeros
int n = 10; // size of the array;

int b = 0;


while (b != n) {
  int e = b;     
  while (++e < n && a[b] < a[e]) {} //while the sequence is increasing, ++e
  while (b != e) { maxLength[b++] = e-b-1; }
}
于 2012-10-18T08:27:18.100 に答える