python - 在无序列表中查找最长的有序序列

Question

我试图在无序列表中找到最长的序列并返回它们的索引。有改进的余地吗？我怎样才能找出最坏情况下的运行时间？我对算法和运行时间很陌生。谢谢!

def find_longest_array(array):
    start = 0
    end = 0
    for left in range(len(array)):
        for right in range(left + 1, len(array)):
            sub_array = array[left:right+1]
            if sorted(sub_array) == sub_array:
                if len(sub_array) > end - start:
                    start, end = left, right
                if end == len(array):
                    return start, end
            else:
                break
    return start, end

Answer 1

您的程序运行时间为 O(n^3 log n)，效率很低。

我们如何得出 O(n^3 log n) 的数字？

1. 您考虑每个子数组一次:有 n^2 个子数组。
2. 然后，您对每个数组进行排序并将其与自身进行比较:每个数组为 nlogn。

---

对此有一个线性时间方法。

令 dp[i] 表示在位置 i 处结束的最长有序序列。

然后:

dp[i] 可以由

构成

• 要么继续前一个以 i - 1 结尾的序列(只有当 arr[i] >= arr[i - 1] 时才有可能，以便保持顺序)

• 或在此时开始一个新的有序序列。

因此，计算 dp[i] = (dp[i - 1] + 1) 如果 arr[i] >= arr[i - 1] or 1 对于所有 i ≠ 0.

最后，返回所有dp[i]中的最大值。

如果您想返回最大数组的实际左右边界，您可以从 i 向后迭代，其中 i 是最大的 dp[i] 。

---

事实上，您可以完全取消 dp，只跟踪当前序列的长度和最大序列的长度和位置到目前为止看到的序列。

但我觉得这种方式更容易理解，也更容易正确书写。