在数组中找到最长的升序(Python)

概述比如,给你一组数字 nums = [2, 5, 3, 3, 4, 6] 并且希望获得尽可能长的数字序列,这些数字在维持其顺序的同时是提升的,但不一定是结果. 所以最长的数字数组,其中An< 1.在这种情况下： [2, 3, 4, 6] 我通过递归和循环完成了这项工作,测试了所有可能性.然而,对于较大的阵列而言,这需要花费太多时间 所以我的问题是,是否有更好/更快的方法来做到这一点. 提前致谢！ 这 比如,给你一组数字

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

并且希望获得尽可能长的数字序列,这些数字在维持其顺序的同时是提升的,但不一定是结果.

所以最长的数字数组,其中An< 1.在这种情况下：

[2,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 maximumdef 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,arr))    return 1 + best

解决方法 我的解决方案

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))

总结

以上是内存溢出为你收集整理的在数组中找到最长的升序(Python)全部内容，希望文章能够帮你解决在数组中找到最长的升序(Python)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。