c - 配列から最大のソート済みサブ配列を取得するアルゴリズム

Question

C で何かをしようとしていますが、別の配列に含まれる最大の次元ごとに並べ替えられた配列を返すアルゴリズムが必要です。たとえば、次の配列があるとします。

A[5] = {5, 2, 3, 1, 4}

返されるはずです：

2, 3, 4

効率的な実装は考えられません。アイデアはありますか？ありがとうございました。:)

Answer 1

あなたの問題は「最長増加サブシーケンス」として知られています。

動的計画法を利用したアルゴリズムは、ここで見つけることができ、適切な説明があります。の最適な漸近複雑度がありO(nlogn)ます。

基本的な考え方は、長さのサブシーケンスの可能な限り最後の要素 (またはそのインデックス) を追跡することですi。次の要素を処理するときは、配列mをチェックして、次のいずれかがあるかどうかを確認します。

• ある程度の長さのより良い (つまり、より小さい) 可能性のある最後の要素を見つけましたi
• そうしないと、これまでよりも長いシーケンスが見つかりました。

Answer 2

最長増加サブシーケンスのウィキペディアページから:

 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)

これは C ではありませんが、C でコーディングするのは簡単なはずです。