查找數組（Python）的最長上升序列

Question

你給出的數字陣列，說

nums = [2, 5, 3, 3, 4, 6] 

，並希望得到的數字，正在上升的最長可能的序列，雖然不一定隨之而來的，而維持他們的秩序。

所以號碼，其中A _Ñ <甲 _{n + 1個}的最長陣列。在這種情況下：

[2, 3, 4, 6] 

我已經通過遞歸和循環完成了這項工作，測試了每種可能性。然而，這對於較大的陣列來說太耗費時間了，所以我的問題是，是否有更好/更快的方法來做到這一點。

在此先感謝！

這裏是我以前的代碼，它返回的最後一個數組的長度

def bestLine(arr): 
    maximum = 0 
    for i in range(0, len(arr)): 
     if (len(arr)-i < maximum): 
      break 
     maximum = max(maximum, f(i, len(arr), arr)) 
    return maximum 

def f(start, end, arr): 
    best = 0 
    for i in range(start+1, end): 
     if (end-i < best): 
      break 
     if (arr[i] > arr[start]): 
      best = max(best, f(i, end, arr)) 
    return 1 + best 

Answer 1

我的解決辦法：

def best_sequence_length(arr): 
    '''Find length of the longest ascending sequence in an array''' 
    arr_length = len(arr) 
    if arr_length <= 1: 
     return arr_length 
    longest = [1] # will store the lengths of the longest sequence ending on this index 
    best_idx_at_all = 0 
    for idx in range(1, arr_length): 
     best_len_so_far = 1 
     back = -1 
     for i in range(len(longest)+1): 
      if arr[i] < arr[idx] and best_len_so_far <= longest[i]: 
       best_len_so_far = longest[i] + 1 
       back = i 
     longest.append(longest[back]+1 if back > -1 else 1) 
     if longest[best_idx_at_all] < longest[idx]: 
      best_idx_at_all = idx 
    return longest[best_idx_at_all] 

這也許不是很「Python化」（它類似於C或甚至Fortran代碼:-)，但它具有O（n^2）的複雜性。

如果你想獲得最長的序列本身，而不僅僅是它的長度（可能是模糊的），上面的功能只需要稍作修改：

def best_sequence(arr): 
    '''Find longest ascending sequence in an array''' 
    arr_length = len(arr) 
    if arr_length <= 1: 
     return arr 
    longest = [1] # will store the length of the longest sequence ending on this index 
    back_link = [-1] # link to the previous element in the longest sequence or -1 
    best_idx_at_all = 0 
    for idx in range(1, arr_length): 
     best_len_so_far = 1 
     back = -1 
     for i in range(len(longest)+1): 
      if arr[i] < arr[idx] and best_len_so_far <= longest[i]: 
       best_len_so_far = longest[i] + 1 
       back = i 
     back_link.append(back) 
     longest.append(longest[back]+1 if back > -1 else 1) 
     if longest[best_idx_at_all] < longest[idx]: 
      best_idx_at_all = idx 

    nxt = best_idx_at_all 
    result = [] 
    while nxt >= 0: 
     result.append(arr[nxt]) 
     nxt = back_link[nxt] 

    return list(reversed(result))