最长上升子序列（LIS）详解

一、问题理解

1. 什么是上升子序列？

在一个数组中，一个子序列是保持相对顺序但不一定连续的元素序列。如果这个子序列中每个元素都严格大于前一个元素，就称为上升子序列。

2. 示例

数组: [10, 9, 2, 5, 3, 7, 101, 18]
最长上升子序列: [2, 5, 7, 101] 或 [2, 5, 7, 18]
长度: 4

二、动态规划解法（O(n²)）

1. 动态规划思想

• dp[i]：表示以 nums[i] 结尾的最长上升子序列的长度
• 对于每个位置 i，我们需要检查所有 j < i：
  • 如果 nums[j] < nums[i]：说明可以在以 nums[j] 结尾的上升子序列后面加上 nums[i]
  • 更新 dp[i] = max(dp[i], dp[j] + 1)

2. 完整代码

def lengthOfLIS(nums):
	"""
    动态规划解法
    时间复杂度：O(n²)，空间复杂度：O(n)
    """
    # 边界情况：空数组
    if not nums:
        return 0
    
    n = len(nums)
    
    # 步骤1：初始化dp数组
    # 每个元素自身就是一个长度为1的上升子序列
    dp = [1] * n # 创建了一个长度为 n 的列表，每个元素都是 1，每个元素本身就是一个长度为1的上升子序列
    
    # 步骤2：动态规划计算
    # 要记住：i 是当前元素，j 是前面的元素
# 我们需要检查前面的元素是否比当前元素小
    for i in range(1, n):  # 从第二个元素开始
        for j in range(i):  # 检查i之前的所有元素
            # 如果nums[j] < nums[i]，说明nums[i]可以接在nums[j]后面
            if nums[j] < nums[i]:
                # 更新dp[i]：取当前dp[i]和dp[j]+1的较大值
                dp[i] = max(dp[i], dp[j] + 1)
    
    # 步骤3：返回最大值
    return max(dp)

“for i in range(1, n):”从索引 1 开始，到索引 n-1 结束，依次遍历数组的每个元素（从第二个元素到最后一个元素）。
为什么从1开始？
（1）没有更前面的元素可以比较
（2）因为dp[0]已经确定了：以nums[0]结尾的LIS长度就是1（因为第一个元素的 LIS 长度总是 1，不需要比较就能确定）
（3）如果写 for j in range(0)，这个循环根本不会执行

“for j in range(i):”对于当前正在处理的元素 nums[i]，检查它之前的所有元素 nums[j]（j < i）。

range(i) 生成什么？
# 当 i=1 时：range(1) → 只生成 0
# 当 i=2 时：range(2) → 生成 0, 1
# 当 i=3 时：range(3) → 生成 0, 1, 2
# 当 i=4 时：range(4) → 生成 0, 1, 2, 3

为什么检查前面的元素？

因为上升子序列要求后面的元素比前面的大。要计算 dp[i]（以 nums[i] 结尾的最长长度），我们需要知道：

有哪些前面的元素比 nums[i] 小

那些元素对应的最长长度是多少

“dp = [1] * n”为什么初始化为1？

在最长上升子序列问题中，dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。

每个元素本身就是一个长度为1的上升子序列（只包含自己）。所以初始时，每个位置的LIS长度至少为1。

# 例如：nums = [3, 1, 4, 2]
# 每个元素自身就是一个上升子序列：
# 3 → [3]       长度=1
# 1 → [1]       长度=1  
# 4 → [4]       长度=1
# 2 → [2]       长度=1

# 所以初始dp值都是1：
dp = [1, 1, 1, 1]

range(start, stop, step)

参数说明：
start: 起始值（包含）
stop: 结束值（不包含）
step: 步长（默认1）

max()函数返回参数中的最大值

算法逻辑：

（1）外层循环处理每个元素 nums[i]（从第二个开始）

（2）内层循环让 nums[i] 检查它前面的所有元素 nums[j]（j < i）

（3）如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 后面

（4）接在后面后，长度就是 dp[j] + 1

（5）在所有可能的 j 中，取最大的长度

3. 完整执行过程示例

示例：nums = [3, 1, 4, 2]

数组： [3, 1, 4, 2]
索引：  0  1  2  3

初始状态：

dp = [1, 1, 1, 1]  # 每个元素自身长度都是1

第一轮外层循环：i=1

处理元素：nums[1] = 1

内层循环：for j in range(1):

• j=0: 检查 nums[0]=3 < nums[1]=1？
  • 3 < 1？ ❌ 不成立
  • 所以不更新 dp[1]
  • dp[1] 保持为 1

当前 dp 状态：

dp = [1, 1, 1, 1]

第二轮外层循环：i=2

处理元素：nums[2] = 4

内层循环：for j in range(2):

• j=0: 检查 nums[0]=3 < nums[2]=4？

  • 3 < 4？ ✅ 成立
  • dp[2] = max(dp[2]=1, dp[0]+1=1+1=2) = 2

• j=1: 检查 nums[1]=1 < nums[2]=4？

  • 1 < 4？ ✅ 成立
  • dp[2] = max(dp[2]=2, dp[1]+1=1+1=2) = 2

当前 dp 状态：

dp = [1, 1, 2, 1]
解释：
- dp[0]=1: 以3结尾的最长长度是1
- dp[1]=1: 以1结尾的最长长度是1
- dp[2]=2: 以4结尾的最长长度是2（可以接在3或1后面）

第三轮外层循环：i=3

处理元素：nums[3] = 2

内层循环：for j in range(3):

• j=0: 检查 nums[0]=3 < nums[3]=2？

  • 3 < 2？ ❌ 不成立

• j=1: 检查 nums[1]=1 < nums[3]=2？

  • 1 < 2？ ✅ 成立
  • dp[3] = max(dp[3]=1, dp[1]+1=1+1=2) = 2

• j=2: 检查 nums[2]=4 < nums[3]=2？

  • 4 < 2？ ❌ 不成立

最终 dp 状态：

dp = [1, 1, 2, 2]
解释：
- dp[3]=2: 以2结尾的最长长度是2（接在1后面）

最终结果：max(dp) = 2

4. 可视化执行过程

nums: [10, 9, 2, 5, 3, 7, 101, 18]
dp:   [1,  1, 1, 1, 1, 1,  1,   1]  # 初始化

i=1 (nums[1]=9):
  j=0: 10<9? False → dp[1]保持1
dp: [1, 1, 1, 1, 1, 1, 1, 1]

i=2 (nums[2]=2):
  j=0: 10<2? False
  j=1: 9<2? False
dp[2]保持1

i=3 (nums[3]=5):
  j=0: 10<5? False
  j=1: 9<5? False
  j=2: 2<5? True → dp[3]=max(1, dp[2]+1=2)=2
dp: [1, 1, 1, 2, 1, 1, 1, 1]

i=4 (nums[4]=3):
  j=0: 10<3? False
  j=1: 9<3? False
  j=2: 2<3? True → dp[4]=max(1, dp[2]+1=2)=2
  j=3: 5<3? False
dp: [1, 1, 1, 2, 2, 1, 1, 1]

i=5 (nums[5]=7):
  j=0: 10<7? False
  j=1: 9<7? False
  j=2: 2<7? True → dp[5]=max(1, dp[2]+1=2)=2
  j=3: 5<7? True → dp[5]=max(2, dp[3]+1=3)=3
  j=4: 3<7? True → dp[5]=max(3, dp[4]+1=3)=3
dp: [1, 1, 1, 2, 2, 3, 1, 1]

i=6 (nums[6]=101):
  j=0: 10<101? True → dp[6]=max(1, dp[0]+1=2)=2
  j=1: 9<101? True → dp[6]=max(2, dp[1]+1=2)=2
  j=2: 2<101? True → dp[6]=max(2, dp[2]+1=2)=2
  j=3: 5<101? True → dp[6]=max(2, dp[3]+1=3)=3
  j=4: 3<101? True → dp[6]=max(3, dp[4]+1=3)=3
  j=5: 7<101? True → dp[6]=max(3, dp[5]+1=4)=4
dp: [1, 1, 1, 2, 2, 3, 4, 1]

i=7 (nums[7]=18):
  j=0: 10<18? True → dp[7]=max(1, dp[0]+1=2)=2
  j=1: 9<18? True → dp[7]=max(2, dp[1]+1=2)=2
  j=2: 2<18? True → dp[7]=max(2, dp[2]+1=2)=2
  j=3: 5<18? True → dp[7]=max(2, dp[3]+1=3)=3
  j=4: 3<18? True → dp[7]=max(3, dp[4]+1=3)=3
  j=5: 7<18? True → dp[7]=max(3, dp[5]+1=4)=4
  j=6: 101<18? False
dp: [1, 1, 1, 2, 2, 3, 4, 4]

最终：max(dp) = 4

三、优化解法（O(n log n) - 贪心+二分查找）

1. 算法思想

维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的所有上升子序列中，最小的末尾元素值。

• 这个数组一定是递增的（可以用反证法证明）
• 对于每个新元素 num，在 tails 中二分查找第一个大于等于 num 的位置
  • 如果找到，用 num 替换该位置的值（因为可以保持更小的末尾元素）
  • 如果没找到（num 比所有末尾都大），就追加到 tails 末尾

2. 完整代码

def lengthOfLIS_optimized(nums):
    """
    贪心+二分查找优化
    时间复杂度：O(n log n)，空间复杂度：O(n)
    """
    if not nums:
        return 0
    
    tails = []  # tails[i]: 长度为i+1的上升子序列的最小末尾元素
    
    for num in nums:
        # 在tails中二分查找第一个大于等于num的位置
        left, right = 0, len(tails)
        
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        # 如果left等于tails长度，说明num比所有末尾都大，追加到末尾
        if left == len(tails):
            tails.append(num)
        else:
            # 否则，用num替换tails[left]
            tails[left] = num
    
    return len(tails)

3. 算法详解

tails数组的含义：tails[i] = 长度为i+1的上升子序列的最小末尾元素值

例子：nums = [10, 9, 2, 5, 3, 7, 101, 18]

处理10: tails = [] → 追加 → tails = [10]
处理9:  9 < 10，替换 → tails = [9]
处理2:  2 < 9，替换 → tails = [2]
处理5:  5 > 2，追加 → tails = [2, 5]
处理3:  3在2和5之间，替换5 → tails = [2, 3]
处理7:  7 > 3，追加 → tails = [2, 3, 7]
处理101: 101 > 7，追加 → tails = [2, 3, 7, 101]
处理18: 18在7和101之间，替换101 → tails = [2, 3, 7, 18]

最终长度: 4

注意：tails数组不一定是真正的LIS，但长度一定是LIS的长度
这里tails = [2, 3, 7, 18]，但实际LIS可能是[2, 5, 7, 101]或[2, 5, 7, 18]
我们只关心长度，不关心具体序列

四、力扣对应题目

1. 力扣 300. 最长递增子序列 ⭐⭐

• 链接：https://leetcode.cn/problems/longest-increasing-subsequence/
• 难度：中等
• 题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 动态规划解法（O(n²)）
        if not nums:
            return 0
        
        n = len(nums)
        dp = [1] * n
        
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)
    
    def lengthOfLIS_optimized(self, nums: List[int]) -> int:
        # 贪心+二分查找解法（O(n log n)）
        if not nums:
            return 0
        
        tails = []
        
        for num in nums:
            # 二分查找第一个大于等于num的位置
            left, right = 0, len(tails)
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            
            if left == len(tails):
                tails.append(num)
            else:
                tails[left] = num
        
        return len(tails)

2. 力扣 673. 最长递增子序列的个数 ⭐⭐⭐

• 链接：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
• 难度：中等
• 题目：给定一个未排序的整数数组，找到最长递增子序列的个数

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        """
        动态规划：记录以每个位置结尾的最长递增子序列的长度和个数
        """
        if not nums:
            return 0
        
        n = len(nums)
        # lengths[i]: 以nums[i]结尾的最长递增子序列的长度
        # counts[i]: 以nums[i]结尾的最长递增子序列的个数
        lengths = [1] * n
        counts = [1] * n
        
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if lengths[j] + 1 > lengths[i]:
                        # 找到更长的序列
                        lengths[i] = lengths[j] + 1
                        counts[i] = counts[j]
                    elif lengths[j] + 1 == lengths[i]:
                        # 找到相同长度的序列，累加个数
                        counts[i] += counts[j]
        
        # 找到最长长度
        max_len = max(lengths)
        
        # 统计所有长度为max_len的序列个数
        result = 0
        for i in range(n):
            if lengths[i] == max_len:
                result += counts[i]
        
        return result

3. 力扣 354. 俄罗斯套娃信封问题 ⭐⭐⭐

• 链接：https://leetcode.cn/problems/russian-doll-envelopes/
• 难度：困难
• 题目：给定一些信封的宽度和高度，如果一个信封的宽度和高度都比另一个大，则可以套进去。求最多能套多少层
• 关键：先按宽度排序，宽度相同按高度降序排序，然后对高度求LIS

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        """
        先按宽度升序，宽度相同按高度降序
        然后对高度序列求LIS
        """
        if not envelopes:
            return 0
        
        # 排序：宽度升序，宽度相同则高度降序
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        
        # 提取高度序列
        heights = [h for _, h in envelopes]
        
        # 对高度序列求LIS（使用贪心+二分优化）
        tails = []
        for height in heights:
            left, right = 0, len(tails)
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < height:
                    left = mid + 1
                else:
                    right = mid
            
            if left == len(tails):
                tails.append(height)
            else:
                tails[left] = height
        
        return len(tails)

4. 力扣 334. 递增的三元子序列 ⭐⭐

• 链接：https://leetcode.cn/problems/increasing-triplet-subsequence/
• 难度：中等
• 题目：给定一个整数数组，判断数组中是否存在长度为 3 的递增子序列

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        """
        贪心法：维护两个最小值
        时间复杂度：O(n)，空间复杂度：O(1)
        """
        if len(nums) < 3:
            return False
        
        # 维护两个最小值
        first = float('inf')  # 最小值
        second = float('inf') # 第二小的值
        
        for num in nums:
            if num <= first:
                first = num  # 更新最小值
            elif num <= second:
                second = num  # 更新第二小值
            else:
                # 找到了第三个数，比first和second都大
                return True
        
        return False

五、变种问题

1. 最长非递减子序列

def lengthOfNonDecreasingSubsequence(nums):
    """
    非递减（允许相等）子序列
    只需修改判断条件
    """
    if not nums:
        return 0
    
    n = len(nums)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if nums[j] <= nums[i]:  # 修改这里：允许相等
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

2. 输出最长上升子序列本身

def longestIncreasingSubsequence(nums):
    """
    返回最长上升子序列本身（而不只是长度）
    """
    if not nums:
        return []
    
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n  # 记录前驱元素索引
    
    # 计算dp和prev
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    
    # 找到最长子序列的结尾位置
    max_len = max(dp)
    end_index = dp.index(max_len)
    
    # 回溯构建序列
    result = []
    while end_index != -1:
        result.append(nums[end_index])
        end_index = prev[end_index]
    
    # 反转得到正序
    return result[::-1]

# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longestIncreasingSubsequence(nums))  # 可能输出 [2, 5, 7, 101] 或 [2, 5, 7, 18]

3. 最长上升子序列的优化（保存路径）

def lengthOfLIS_with_path(nums):
    """
    使用tails数组同时保存长度和路径
    """
    if not nums:
        return 0, []
    
    tails = []  # tails[i]: 长度为i+1的上升子序列的最小末尾元素
    indices = []  # indices[i]: 对应tails[i]在nums中的索引
    prev = [-1] * len(nums)  # 记录前驱索引
    
    for i, num in enumerate(nums):
        # 二分查找
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        if left == len(tails):
            tails.append(num)
            indices.append(i)
        else:
            tails[left] = num
            indices[left] = i
        
        # 记录前驱（left>0时，前驱是indices[left-1]）
        if left > 0:
            prev[i] = indices[left - 1]
    
    # 构建路径
    result = []
    curr = indices[-1]
    while curr != -1:
        result.append(nums[curr])
        curr = prev[curr]
    
    return len(tails), result[::-1]

六、复杂度分析

方法	时间复杂度	空间复杂度	优点	缺点
动态规划	O(n²)	O(n)	简单易懂，易于理解	效率低，不适合大数据量
贪心+二分	O(n log n)	O(n)	效率高，适合大数据量	理解难度大，不直接输出序列

七、常见错误与调试

错误1：忘记处理空数组

# ❌ 错误：没有检查空数组
def lengthOfLIS(nums):
    n = len(nums)  # 如果nums为空，n=0
    dp = [1] * n   # 没问题，空列表
    for i in range(1, n):  # range(1, 0)不执行
        ...
    return max(dp)  # ❌ max()在空列表上会报错

# ✅ 正确：先检查空数组
def lengthOfLIS(nums):
    if not nums:
        return 0
    ...

错误2：初始化dp错误

# ❌ 错误：初始化为0
dp = [0] * n  # 每个元素自身长度应该是1，不是0

# ✅ 正确：初始化为1
dp = [1] * n

错误3：二分查找边界错误

# ❌ 错误：二分查找实现错误
while left <= right:  # 应该是 left < right
    ...

# ✅ 正确
while left < right:
    ...

八、面试常见问题

Q1：为什么动态规划解法是O(n²)？

A：因为有两层循环，外层遍历每个元素(i从0到n-1)，内层对于每个i又遍历所有j(<i)。总共比较次数是1+2+3+…+(n-1)=n(n-1)/2，所以是O(n²)。

Q2：贪心+二分查找为什么正确？

A：核心思想是维护一个tails数组，其中tails[i]表示长度为i+1的所有上升子序列中末尾元素的最小值。这个数组是递增的（可以用反证法证明）。对于每个新元素，我们只需要更新第一个大于等于它的位置，这样就能保证tails数组始终保持最小末尾值。

Q3：什么时候用动态规划，什么时候用贪心+二分？

A：

• 如果只需要长度，并且数组规模较大（n>1000），用贪心+二分（O(n log n)）
• 如果需要具体的子序列，或者数组规模较小，用动态规划（O(n²)）
• 面试中建议先讲动态规划，再提优化方法

Q4：如何输出所有的最长上升子序列？

A：这是一个更复杂的问题，需要记录所有的路径。可以使用回溯法，但时间复杂度会很高。

九、练习题

练习1：实现两种解法

# 分别用动态规划和贪心+二分实现LIS
def test_LIS():
    test_cases = [
        ([10, 9, 2, 5, 3, 7, 101, 18], 4),
        ([0, 1, 0, 3, 2, 3], 4),
        ([7, 7, 7, 7, 7, 7, 7], 1),
        ([], 0),
        ([1], 1),
        ([3, 2, 1], 1),
        ([1, 3, 6, 7, 9, 4, 10, 5, 6], 6),
    ]
    
    for nums, expected in test_cases:
        dp_result = lengthOfLIS(nums)
        opt_result = lengthOfLIS_optimized(nums)
        print(f"{nums} → DP:{dp_result}, OPT:{opt_result}, Expected:{expected}")
        assert dp_result == expected
        assert opt_result == expected

test_LIS()

练习2：最长连续递增子序列

def findLengthOfLCIS(nums):
    """
    最长连续递增子序列（要求连续）
    力扣674：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
    """
    if not nums:
        return 0
    
    max_len = 1
    curr_len = 1
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            curr_len += 1
            max_len = max(max_len, curr_len)
        else:
            curr_len = 1
    
    return max_len

练习3：最长递增子序列的变种

def longestIncreasingSubsequenceWithThreshold(nums, threshold):
    """
    找到最长上升子序列，但要求相邻元素差值不超过threshold
    """
    if not nums:
        return 0
    
    n = len(nums)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and abs(nums[j] - nums[i]) <= threshold:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

十、总结

最长上升子序列（LIS）是动态规划的经典问题：

核心解法：

1. 动态规划（O(n²)）：

   • 状态定义：dp[i] 表示以 nums[i] 结尾的最长上升子序列长度
   • 状态转移：dp[i] = max(dp[i], dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]
   • 初始化：dp[i] = 1
   • 结果：max(dp)

2. 贪心+二分查找（O(n log n)）：

   • 维护 tails 数组：tails[i] 是长度为 i+1 的所有上升子序列中末尾元素的最小值
   • 对于每个元素，二分查找在 tails 中的位置并更新
   • 结果：len(tails)

相关力扣题目：

1. 300 - 最长递增子序列（基础）
2. 673 - 最长递增子序列的个数（进阶）
3. 354 - 俄罗斯套娃信封问题（二维LIS）
4. 334 - 递增的三元子序列（简化版）

面试要点：

1. 理解两种解法的时间复杂度和空间复杂度
2. 能够解释贪心+二分查找的正确性
3. 能够处理边界情况（空数组、单个元素等）
4. 了解变种问题（连续、非递减、带限制等）