python - 查找数组中最长的升序(Python)

Question

给你一个数字数组，比方说

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

并希望获得尽可能长的数字序列，这些数字是递增的，但不一定是结果，同时保持它们的顺序。

所以最长的数字数组，其中 A_n < 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]

这可能不是很“pythonic”(它类似于 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))