时间戳

首页 > 解决方案 > 如何获得最长的子升序数组，不一定必须是连续的

python - 如何获得最长的子升序数组，不一定必须是连续的

问题描述

我想从一个大列表中获取最长的子数组。为简单起见，我只显示数组的一部分：

a = [1263, 1270, 1265, 1267, 1266, 1269, 1271, 1272, 1268, 1264, 1288, 1289, 1261, 1262, 1284, 1277, 1278, 1281, 1273, 1279, 1280, 1296]

输出应按升序保留尽可能多的元素。输出不一定必须是连续的。我手动得到了输出，发现它应该有 11 个元素：

[1263, 1265, 1266, 1269, 1271, 1272, 1277, 1278, 1279, 1280, 1296]

但是，我只能从我的代码中获取 7 个元素数组：

def get_ascending_sub_array(arr):
    if not arr:
        return arr
    if len(arr) == 1:
        return arr
    else:
        sub_arr = [ arr[0] ]
        for i in range(1,len(arr)):
            if arr[i] > sub_arr[-1]:
                sub_arr.append(arr[i])
        return sub_arr



def get_longest_sub_ascending_array(arr):
    outarr = []
    if not arr:
        return arr
    if len(arr) == 1:
        return arr
    max_len = 0
    max_arr = []
    for i in range(len(arr)):
        if len(arr[i:]) > max_len:
            arr_start_at_i = get_longest_sub_ascending_array(arr[i:])
            if len(arr_start_at_i) > max_len:
                max_len = max_len
                max_arr = get_ascending_sub_array(arr[i:])
    outarr = max_arr
    return outarr

print get_ascending_sub_array(a)

输出：

[1263, 1270, 1271, 1272, 1288, 1289, 1296]

我的代码有什么问题？

感谢您的任何建议。

最后，我从这里找到了这个答案：

# Dynamic Programming solution to construct Longest 
# Increasing Subsequence 

# Utility function to print LIS 
def printLIS(arr): 
    arr = list(arr)
    for x in arr: 
        print x,
    print 
    print len(arr)

# Function to construct and print Longest Increasing 
# Subsequence 
def constructPrintLIS(arr, n): 
    arr = list(arr)
    n = int(n)

    # L[i] - The longest increasing sub-sequence 
    # ends with arr[i] 
    l = [[] for i in range(n)] 

    # L[0] is equal to arr[0] 
    l[0].append(arr[0]) 

    # start from index 1 
    for i in range(1, n): 

        # do for every j less than i 
        for j in range(i): 

            # L[i] = {Max(L[j])} + arr[i] 
            # where j < i and arr[j] < arr[i] 
            if arr[i] > arr[j] and (len(l[i]) < len(l[j]) + 1): 
                l[i] = list(l[j]) #.copy() 

        # L[i] ends with arr[i] 
        l[i].append(arr[i]) 

    # L[i] now stores increasing sub-sequence of 
    # arr[0..i] that ends with arr[i] 
    maxx = l[0] 

    # LIS will be max of all increasing sub- 
    # sequences of arr 
    for x in l: 
        if len(x) > len(maxx): 
            maxx = x 

    # max will contain LIS 
    printLIS(maxx) 



# This code is contributed by 
# sanjeev2552 





a = [1263, 1270, 1265, 1267, 1266, 1269, 1271, 
     1272, 1268, 1264, 1288, 1289, 1261, 1262, 1284, 
     1277, 1278, 1281, 1273, 1279, 1280, 1296]

print constructPrintLIS(a, len(a))

标签： pythonarraysalgorithmrecursion

解决方案

您描述的问题是最长递增子序列问题。

该算法在上面的 Wikipedia 链接中进行了描述。我建议您使用他们描述的算法，该算法运行得相当快（O(n log n)）。

如果你不太了解它，你也可以使用动态规划算法计算最长公共子序列。它将在 中运行，这是次优的，但仍适用于相对较小的输入。arrsorted(arr)O(n²)

推荐阅读