最长递增子序列
"""
Author : Mehdi ALAOUI
This is a pure Python implementation of Dynamic Programming solution to the longest
increasing subsequence of a given sequence.
The problem is :
Given an array, to find the longest and increasing sub-array in that given array and
return it.
Example: [10, 22, 9, 33, 21, 50, 41, 60, 80] as input will return
[10, 22, 33, 41, 60, 80] as output
"""
from __future__ import annotations
def longest_subsequence(array: list[int]) -> list[int]: # This function is recursive
"""
Some examples
>>> longest_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80])
[10, 22, 33, 41, 60, 80]
>>> longest_subsequence([4, 8, 7, 5, 1, 12, 2, 3, 9])
[1, 2, 3, 9]
>>> longest_subsequence([9, 8, 7, 6, 5, 7])
[8]
>>> longest_subsequence([1, 1, 1])
[1, 1, 1]
>>> longest_subsequence([])
[]
"""
array_length = len(array)
# If the array contains only one element, we return it (it's the stop condition of
# recursion)
if array_length <= 1:
return array
# Else
pivot = array[0]
is_found = False
i = 1
longest_subseq: list[int] = []
while not is_found and i < array_length:
if array[i] < pivot:
is_found = True
temp_array = [element for element in array[i:] if element >= array[i]]
temp_array = longest_subsequence(temp_array)
if len(temp_array) > len(longest_subseq):
longest_subseq = temp_array
else:
i += 1
temp_array = [element for element in array[1:] if element >= pivot]
temp_array = [pivot, *longest_subsequence(temp_array)]
if len(temp_array) > len(longest_subseq):
return temp_array
else:
return longest_subseq
if __name__ == "__main__":
import doctest
doctest.testmod()
关于此算法
问题陈述
给定一个整数数组 A，找到最长递增子序列 (LIS) 的长度，使得子序列的所有元素按递增顺序排序。递增子序列包含元素 A[i] 和 A[j]，仅当 i < j 且 A[i] < A[j]。
方法
解决方案背后的基本思想是在给定时间点跟踪所有活动的子序列。根据当前正在考虑的数字，更新这些活动列表。为了理解这个过程，让我们解决一个例子。
A = {2,8,7}
Monotonically increasing subsequences are {2,8} and {2,7}
如果我们再添加一个元素 11 会怎么样？
A = {2,8,7,11}
Monotonically increasing subsequences are {2,8,11} and {2,7,11}
如果一个新的元素 9 被添加到数组中会怎么样？现在会发生什么？如果我们添加到子序列中，最长子序列的长度仍然是 3。
A = {2,8,7,11,9}
Monotonically increasing subsequences are {2,8,9} and {2,7,9}
对于每个正在考虑的元素，要做的决定是，我们是否创建包含元素 9 的长度为 3 的新活动子序列，或者继续使用 11。如果下一个元素是 10，我们知道将 9 添加到子序列会导致更长的子序列，而不是保留 11。
我们如何决定何时替换和何时继续使用子序列列表中的旧元素？
如果 A[i] > E，我们将一个新的数字 A[i] 添加到序列中，E 是子序列中的最后一个元素，如果存在一个数字 A[j]，使得 E > A[i] < A[j]，这意味着新数字落在 A[j] 和 E 之间，我们将用 A[i] 替换一个数字。
如果 A[i] 小于当前子序列列表中的所有元素怎么办？在这种情况下，我们必须创建一个新的列表并将 A[i] 添加到其中。不变式是维护递增序列的列表并根据下一个数字更新它们。每次要添加一个新元素时，按其长度降序扫描所有子序列列表。以下算法展示了如何在现有列表中添加/替换新元素或使用它们创建新列表。
1. If A[i] is the smallest among all end candidates of active lists, start a new active list with A[i] of length 1.
2. If A[i] is largest among all end candidates of active lists, clone the largest active list, and append A[i] to it.
3. If A[i] is in between, find the list with the largest end number that is smaller than A[i]. Clone and append A[i] to this list.
4. Discard all other lists of the same length as that of this modified list.
时间复杂度
O(N * LogN) 在任何情况下
O(logn) 时间来找到它的上限并将其放在正确的位置
空间复杂度
O(N) 对于数组中的每个元素
例子
让我们举个例子，看看它如何使用数组 A = [ 0, 8, 4, 12, 2, 10, 6, 14] 工作。对于 A[0]，没有活动的子序列列表。我们将创建一个新的。
[0,8,4,12,2,10,6,14]
[0]
接下来，我们转到 A[1]，它等于 8。A[i] 大于所有当前列表的末尾，我们将取最长的一个并将 A[1] 附加到它。
[0,8,4,12,2,10,6,14]
[[0],[0,8]]
对于 A[2]，其值为 4，A[i] 小于其中一个列表的末尾，大于另一个列表的末尾。我们将找到末尾小于 A[i] 的列表。在本例中，它是包含 [0] 的第一个列表。克隆它并将 A[2] 附加到它，并丢弃所有其他相同长度的列表。
[0,8,4,12,2,10,6,14]
[[0],[0,4]]
[0,8] is discarded as it is of the same length 2.
对于 A[3]，其值为 12，它与 A[1] 相同，因为它大于所有当前列表的末尾，我们将克隆最长的可用列表并将 A[3] 附加到它。
[0,8,4,12,2,10,6,14]
[[0],[0,4],[0,4,12]]
A[4]，其值为 2，它与 A[2] 相同，克隆末尾最大且小于 A[4] 的列表，将 A[4] 附加到它，并丢弃所有相同长度的列表。
[0,8,4,12,2,10,6,14]
[[0],[0,2],[0,4,12]]
A[5]，其值为 10。与 A[4] 相同。克隆、扩展并丢弃所有相同长度的子序列。列表 = [ [0], [0, 2], [0,2,10] ]，[0, 4, 12] 被丢弃。
A[6] 是 6。与 A[5] 相同。我们将克隆末尾小于 A[6] 的列表，扩展它，并丢弃所有其他相同长度的列表。列表 = [ [0], [0, 2], [0,2,6] ]，[0, 2, 10] 被丢弃。
按照相同的方法，我们将遍历给定数组中的所有数字。给定数组中最长的递增子序列是 [ 0,2,6,14]，长度为 4。
[0,8,4,12,2,10,6,14]
[[0],[0,2],[0,2,6],[0,2,6,14]]
看起来为了维护列表，需要做很多事情，并且需要大量的空间复杂度来存储所有这些列表。我们可以对此进行优化，观察到我们只使用列表的末尾及其大小。我们并不关心它们之前列表中的内容是什么。因此，我们可以将所有列表的末尾存储在辅助数组中，并在其上执行操作吗？该数组在最坏情况下的大小将是 n。
要附加到列表，请在辅助数组中添加另一个元素。要替换，只需覆盖大于当前数字的最小数字即可。要找到大于当前数字的最小数字，我们可以使用二分查找算法。
要找到最长子序列的长度，跟踪辅助数组的长度，因为这将是 LIS 的长度。
