最长递增子序列算法代码

以下是最长递增子序列算法的Python代码：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

其中，`nums`是输入的列表，`dp`是用来存储以第i个元素为结尾的最长递增子序列的长度。算法的时间复杂度为$O(n^2)$。

相关问题

最长递增子序列算法伪代码

以下是最长递增子序列（Longest Increasing Subsequence, LIS）的动态规划算法伪代码：

输入：序列 a，长度为 n

LIS = [1]*n // 初始化 LIS 数组，LIS[i] 表示以 a[i] 结尾的 LIS 长度为 1
for i = 1 to n do
for j = 1 to i-1 do
if a[j] < a[i] then
LIS[i] = max(LIS[i], LIS[j]+1)
输出：max(LIS) // LIS 数组的最大值即为最长递增子序列的长度

其中 max 函数表示取最大值。时间复杂度为 O(n^2)。

Python 最长递增子序列算法

### Python 实现最长递增子序列算法

#### 动态规划方法

一种常见的实现方式是通过动态规划来解决问题。此方法利用数组 `dp` 来记录到当前位置为止的最大递增子序列长度。

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n  # 初始化dp数组，每个位置至少有长度为1的递增子序列
    
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp) if dp else 0

上述代码遍历给定列表中的每一个元素，并尝试找到之前所有小于当前元素的位置，更新对应的 `dp` 值以反映更长的递增子序列的存在[^1]。

对于测试数据 `[10, 22, 9, 33, 21, 50, 41, 60]` ，这段程序会返回最大递增子序列的长度作为结果。

#### 使用二分查找优化的方法

另一种更为高效的解决方案涉及使用额外的空间保存潜在的结果序列并应用二分查找技术：

from bisect import bisect_left

def lis(nums):
    tails = []  # 存储可能成为最终解的一部分的最佳候选者们
    
    for num in nums:
        position = bisect_left(tails, num)  # 找到num应该插入的位置
        
        if position == len(tails):
            tails.append(num)  # 如果找不到合适的位置，则添加到最后面
        else:
            tails[position] = num  # 否则替换掉那个位置上的较大值
            
    return len(tails)  # 返回tails的大小即为所求答案

这种方法的时间复杂度接近 O(N log N)，其中N表示输入数组的长度。它不仅提高了效率而且保持了相同的逻辑框架——寻找尽可能短但仍然能代表整个 LIS 的替代路径[^2]。