算法，從數組中獲取最大的排序子陣列

Question

我想在C中做一些事情，我需要一種算法，返回另一個數組中包含的最大維度明智的排序數組。因此，舉例來說，如果我有以下陣列：

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

它應該返回：

2, 3, 4 

，我想不出任何有效實施。有什麼想法？謝謝。 :)

Answer 1

您的問題被稱爲「longest increasing subsequence」。

利用dynamic programming的算法可以是found here, with a good explanation。它具有最佳的漸近複雜度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.