最长递增子序列

1. 概述

最长递增子序列（Longest Increasing Subsequence，简称LIS）是动态规划领域的经典问题，也是算法面试中的高频考点。该问题要求在给定序列中找到最长的严格递增子序列。

1.1 核心特点

• 经典动态规划问题：具有最优子结构和重叠子问题
• 多种解法：从O(n²)到O(nlogn)的优化过程
• 实际应用广泛：版本控制、数据分析、生物信息学等
• 扩展性强：衍生出多个相关问题

1.2 学习价值

1. 算法思维训练：从暴力到优化的完整思考过程
2. 数据结构应用：二分查找、动态规划的综合运用
3. 面试必备：各大公司算法面试的常见题目
4. 工程实践：实际项目中的序列分析需求

2. 问题定义

2.1 基本定义

给定一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列：从原数组中删除一些（也可以不删除）元素，剩余元素保持原有顺序形成的新序列。

严格递增：对于子序列中的任意两个相邻元素 a[i] 和 a[j]（i < j），都有 a[i] < a[j]。

2.2 示例分析

输入: nums = [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长递增子序列是 [2,3,7,18]，因此长度为 4。

可能的递增子序列：

• [10] → 长度 1
• [9] → 长度 1
• [2,5,7,101] → 长度 4
• [2,3,7,18] → 长度 4 ✓
• [2,5,7,18] → 长度 4

2.3 约束条件

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4
• 子序列必须严格递增
• 需要返回长度，不需要返回具体序列

3. 算法分析

3.1 问题特征分析

最优子结构

设 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度，则：

dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i]

重叠子问题

在计算 dp[i] 时，需要用到之前计算的 dp[j] 值，存在重叠子问题。

3.2 解法复杂度对比

解法	时间复杂度	空间复杂度	特点
暴力递归	O(2^n)	O(n)	指数级，不实用
动态规划	O(n²)	O(n)	经典解法，易理解
二分优化	O(nlogn)	O(n)	最优解法，较难理解
贪心+二分	O(nlogn)	O(n)	实际最快，工程首选

---

4. 暴力解法

4.1 递归思路

对于每个元素，我们有两种选择：

1. 包含当前元素（如果它能形成递增序列）
2. 不包含当前元素

如果选择当前元素，则必有

dfs(i) = max(dfs(j)) + 1 && j < i && nums[j] < nums[i]

public class LISRecursive {
    /**
     * 暴力递归解法
     * 时间复杂度: O(2^n)
     * 空间复杂度: O(n)
     */
    public static int lengthOfLISRecursive(int[] nums) {
        int ans = 0;
        for(int i = 0; i < nums.length; i++) {
            ans = Math.max(ans, dfs(nums, i));
        }
        return ans;
    }
    
    private static int dfs(int[] nums, int index) {
        int ans = 0;
        for (int i = 0; i < index; i++) {
            if (nums[i] < nums[index]) {
                ans = Math.max(ans, dfs(nums, i));
            }
        }
        return ans + 1;
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("递归解法结果: " + lengthOfLISRecursive(nums)); // 输出: 4
    }
}

4.2 记忆化递归

import java.util.HashMap;
import java.util.Map;

public class LISMemo {
    private static Map<String, Integer> memo;
    
    /**
     * 记忆化递归解法
     * 时间复杂度: O(n²)
     * 空间复杂度: O(n²)
     */
    public static int lengthOfLISMemo(int[] nums) {
        memo = new HashMap<>();
        return dfs(nums, 0, -1);
    }
    
    private static int dfs(int[] nums, int index, int prevIndex) {
        if (index == nums.length) {
            return 0;
        }
        
        String key = index + "," + prevIndex;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        // 不包含当前元素
        int result = dfs(nums, index + 1, prevIndex);
        
        // 包含当前元素
        if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
            result = Math.max(result, 1 + dfs(nums, index + 1, index));
        }
        
        memo.put(key, result);
        return result;
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("记忆化递归结果: " + lengthOfLISMemo(nums)); // 输出: 4
    }
}

5. 动态规划解法

5.1 状态定义

dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

5.2 状态转移方程

dp[i] = max(dp[j] + 1) for all j in [0, i-1] where nums[j] < nums[i]

如果没有满足条件的 j，则 dp[i] = 1（单独成为一个子序列）。

5.3 基础实现

import java.util.Arrays;

public class LISDP {
    /**
     * 动态规划解法
     * 时间复杂度: O(n²)
     * 空间复杂度: O(n)
     */
    public static int lengthOfLISDP(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        // 填充 dp 数组
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        // 返回所有位置的最大值
        return Arrays.stream(dp).max().orElse(0);
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("动态规划结果: " + lengthOfLISDP(nums)); // 输出: 4
    }
}

5.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: nums[0]=10 > 9, 不更新
  dp = [1, 1, 1, 1, 1, 1, 1, 1]

i=2, nums[2]=2:
  j=0: nums[0]=10 > 2, 不更新
  j=1: nums[1]=9 > 2, 不更新
  dp = [1, 1, 1, 1, 1, 1, 1, 1]

i=3, nums[3]=5:
  j=0: nums[0]=10 > 5, 不更新
  j=1: nums[1]=9 > 5, 不更新
  j=2: nums[2]=2 < 5, dp[3] = max(1, 1+1) = 2
  dp = [1, 1, 1, 2, 1, 1, 1, 1]

i=4, nums[4]=3:
  j=0: nums[0]=10 > 3, 不更新
  j=1: nums[1]=9 > 3, 不更新
  j=2: nums[2]=2 < 3, dp[4] = max(1, 1+1) = 2
  j=3: nums[3]=5 > 3, 不更新
  dp = [1, 1, 1, 2, 2, 1, 1, 1]

继续执行...
最终: dp = [1, 1, 1, 2, 2, 3, 4, 4]
结果: max(dp) = 4

5.5 返回具体序列

import java.util.*;

public class LISWithSequence {
    /**
     * 返回最长递增子序列的长度和具体序列
     */
    public static class Result {
        public int length;
        public List<Integer> sequence;
        
        public Result(int length, List<Integer> sequence) {
            this.length = length;
            this.sequence = sequence;
        }
    }
    
    public static Result lengthOfLISWithSequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new Result(0, new ArrayList<>());
        }
        
        int n = nums.length;
        int[] dp = new int[n];
        int[] parent = new int[n]; // 记录前驱元素的索引
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        
        int maxLength = 1;
        int maxIndex = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                maxIndex = i;
            }
        }
        
        // 重构序列
        List<Integer> sequence = new ArrayList<>();
        int current = maxIndex;
        while (current != -1) {
            sequence.add(nums[current]);
            current = parent[current];
        }
        
        Collections.reverse(sequence);
        return new Result(maxLength, sequence);
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        Result result = lengthOfLISWithSequence(nums);
        System.out.println("长度: " + result.length + ", 序列: " + result.sequence); // 长度: 4, 序列: [2, 3, 7, 18]
    }
}

---

6. 二分优化解法

6.1 核心思想

维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小尾部元素。

关键洞察：

• 对于相同长度的递增子序列，尾部元素越小，越有利于后续扩展
• tails 数组本身是递增的
• 可以用二分查找快速定位插入位置

6.2 算法步骤

1. 初始化空的 tails 数组
2. 对于每个元素 num：
   • 如果 num 大于 tails 的最后一个元素，直接追加
   • 否则，用二分查找找到第一个 >= num 的位置，进行替换
3. 返回 tails 的长度

6.3 基础实现

import java.util.ArrayList;
import java.util.List;

public class LISBinarySearch {
    /**
     * 二分优化解法
     * 时间复杂度: O(nlogn)
     * 空间复杂度: O(n)
     */
    public static int lengthOfLISBinarySearch(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            // 二分查找第一个 >= num 的位置
            int left = 0, right = tails.size();
            while (left < right) {
                int mid = (left + right) / 2;
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            // 如果找到末尾，说明 num 比所有元素都大，直接追加
            if (left == tails.size()) {
                tails.add(num);
            } else {
                // 否则替换找到的位置
                tails.set(left, num);
            }
        }
        
        return tails.size();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("二分优化结果: " + lengthOfLISBinarySearch(nums)); // 输出: 4
    }
}

6.4 使用内置二分查找

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LISBisect {
    /**
     * 使用 Java 内置 Collections.binarySearch
     */
    public static int lengthOfLISBisect(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            int pos = Collections.binarySearch(tails, num);
            // 如果没找到，binarySearch返回负数，转换为插入位置
            if (pos < 0) {
                pos = -(pos + 1);
            }
            
            if (pos == tails.size()) {
                tails.add(num);
            } else {
                tails.set(pos, num);
            }
        }
        
        return tails.size();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("bisect 结果: " + lengthOfLISBisect(nums)); // 输出: 4
    }
}

6.5 详细执行过程

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

初始: tails = []

num = 10:
  tails 为空，直接追加
  tails = [10]

num = 9:
  二分查找 >= 9 的位置: 位置 0 (tails[0] = 10)
  替换: tails[0] = 9
  tails = [9]

num = 2:
  二分查找 >= 2 的位置: 位置 0 (tails[0] = 9)
  替换: tails[0] = 2
  tails = [2]

num = 5:
  二分查找 >= 5 的位置: 位置 1 (超出范围)
  追加: tails.append(5)
  tails = [2, 5]

num = 3:
  二分查找 >= 3 的位置: 位置 1 (tails[1] = 5)
  替换: tails[1] = 3
  tails = [2, 3]

num = 7:
  二分查找 >= 7 的位置: 位置 2 (超出范围)
  追加: tails.append(7)
  tails = [2, 3, 7]

num = 101:
  二分查找 >= 101 的位置: 位置 3 (超出范围)
  追加: tails.append(101)
  tails = [2, 3, 7, 101]

num = 18:
  二分查找 >= 18 的位置: 位置 3 (tails[3] = 101)
  替换: tails[3] = 18
  tails = [2, 3, 7, 18]

结果: len(tails) = 4

6.6 为什么这样做是正确的？

核心不变量：tails[i] 始终保存长度为 i+1 的递增子序列的最小尾部元素。

证明思路：

1. 单调性：tails 数组始终保持递增
2. 最优性：对于每个长度，我们总是保存最小的尾部元素
3. 可扩展性：较小的尾部元素更容易被后续元素扩展

---

7. 代码实现

7.1 Python 完整实现

class LongestIncreasingSubsequence:
    """
    最长递增子序列的多种实现
    """
    
    @staticmethod
    def dp_solution(nums):
        """
        动态规划解法 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)
    
    @staticmethod
    def binary_search_solution(nums):
        """
        二分优化解法 O(nlogn)
        """
        if not nums:
            return 0
        
        tails = []
        
        for num in 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)
            else:
                tails[left] = num
        
        return len(tails)
    
    @staticmethod
    def get_sequence(nums):
        """
        返回具体的最长递增子序列
        """
        if not nums:
            return []
        
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n
        
        max_length = 1
        max_index = 0
        
        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
                    parent[i] = j
            
            if dp[i] > max_length:
                max_length = dp[i]
                max_index = i
        
        # 重构序列
        sequence = []
        current = max_index
        while current != -1:
            sequence.append(nums[current])
            current = parent[current]
        
        return sequence[::-1]
    
    @staticmethod
    def count_sequences(nums):
        """
        计算最长递增子序列的数量
        """
        if not nums:
            return 0
        
        n = len(nums)
        dp = [1] * n  # 长度
        count = [1] * n  # 数量
        
        max_length = 1
        
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i]:
                        count[i] += count[j]
            
            max_length = max(max_length, dp[i])
        
        # 统计最长长度的序列数量
        result = 0
        for i in range(n):
            if dp[i] == max_length:
                result += count[i]
        
        return result

# 测试所有方法
if __name__ == "__main__":
    test_cases = [
        [10, 9, 2, 5, 3, 7, 101, 18],
        [0, 1, 0, 3, 2, 3],
        [7, 7, 7, 7, 7, 7, 7],
        [1, 3, 6, 7, 9, 4, 10, 5, 6],
        []
    ]
    
    lis = LongestIncreasingSubsequence()
    
    for i, nums in enumerate(test_cases):
        print(f"\n测试用例 {i+1}: {nums}")
        print(f"DP解法长度: {lis.dp_solution(nums)}")
        print(f"二分解法长度: {lis.binary_search_solution(nums)}")
        print(f"具体序列: {lis.get_sequence(nums)}")
        print(f"序列数量: {lis.count_sequences(nums)}")

---

8. 变种问题

8.1 最长非递减子序列

允许相等元素的递增子序列。

def lengthOfLIS_non_decreasing(nums):
    """
    最长非递减子序列（允许相等）
    只需要将 < 改为 <=
    """
    if not nums:
        return 0
    
    tails = []
    
    for num in nums:
        # 查找第一个 > num 的位置（而不是 >= 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)

# 测试
nums = [1, 3, 3, 5, 5, 7]
print(f"非递减子序列长度: {lengthOfLIS_non_decreasing(nums)}")  # 输出: 6

8.2 最长递减子序列

import java.util.ArrayList;
import java.util.List;

public class LongestDecreasingSubsequence {
    /**
     * 最长递减子序列
     * 直接修改算法
     */
    public static int lengthOfLDS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            // 查找第一个 <= num 的位置
            int left = 0, right = tails.size();
            while (left < right) {
                int mid = (left + right) / 2;
                if (tails.get(mid) > num) {  // 改为 >
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            if (left == tails.size()) {
                tails.add(num);
            } else {
                tails.set(left, num);
            }
        }
        
        return tails.size();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {7, 5, 6, 4, 3, 1};
        System.out.println("递减子序列长度: " + lengthOfLDS(nums)); // 输出: 5
    }
}

---

9. LeetCode题目解析

9.1 LeetCode 300. 最长递增子序列

def lengthOfLIS(nums):
    """
    LeetCode 300. 最长递增子序列
    
    解法选择：
    - 数据量小(n <= 100): 动态规划 O(n²)
    - 数据量大(n > 100): 二分优化 O(nlogn)
    """
    if not nums:
        return 0
    
    # 二分优化解法
    tails = []
    
    for num in 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)
        else:
            tails[left] = num
    
    return len(tails)

9.2 LeetCode 354. 俄罗斯套娃信封问题

import java.util.*;

public class RussianDollEnvelopes {
    /**
     * LeetCode 354. 俄罗斯套娃信封问题
     * 
     * 核心思路：
     * 1. 按宽度升序排序，宽度相同时按高度降序排序
     * 2. 对高度数组求最长递增子序列
     * 
     * 时间复杂度: O(nlogn)
     * 空间复杂度: O(n)
     */
    public static int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        
        // 排序：宽度升序，高度降序
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1]; // 高度降序
            }
            return a[0] - b[0]; // 宽度升序
        });
        
        // 提取高度数组
        int[] heights = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) {
            heights[i] = envelopes[i][1];
        }
        
        // 对高度求LIS
        return lengthOfLIS(heights);
    }
    
    private static int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            int left = 0, right = tails.size();
            while (left < right) {
                int mid = (left + right) / 2;
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            if (left == tails.size()) {
                tails.add(num);
            } else {
                tails.set(left, num);
            }
        }
        
        return tails.size();
    }
    
    // 测试
    public static void main(String[] args) {
        int[][] envelopes = {{5,4},{6,4},{6,7},{2,3}};
        System.out.println("最多套娃数量: " + maxEnvelopes(envelopes)); // 输出: 3
    }
}

9.3 LeetCode 673. 最长递增子序列的个数

import java.util.Arrays;

public class NumberOfLIS {
    /**
     * LeetCode 673. 最长递增子序列的个数
     * 
     * 思路：
     * 1. dp[i]: 以nums[i]结尾的最长递增子序列长度
     * 2. count[i]: 以nums[i]结尾的最长递增子序列个数
     * 
     * 时间复杂度: O(n²)
     * 空间复杂度: O(n)
     */
    public static int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int[] dp = new int[n];      // 长度
        int[] count = new int[n];   // 个数
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        
        int maxLength = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        // 找到更长的序列
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        // 找到相同长度的序列
                        count[i] += count[j];
                    }
                }
            }
            
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        // 统计最长长度的序列个数
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLength) {
                result += count[i];
            }
        }
        
        return result;
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 4, 7};
        System.out.println("最长递增子序列个数: " + findNumberOfLIS(nums)); // 输出: 2
    }
}

---

10. 实际应用

10.1 版本控制系统

import java.util.*;

public class VersionControl {
    /**
     * 版本控制中的LIS应用
     */
    
    private List<Map.Entry<String, Integer>> versions;
    
    public VersionControl() {
        this.versions = new ArrayList<>();
    }
    
    /**
     * 添加版本信息
     */
    public void addVersion(String versionNumber, int stabilityScore) {
        versions.add(new AbstractMap.SimpleEntry<>(versionNumber, stabilityScore));
    }
    
    /**
     * 找到最长的稳定升级路径
     * 要求：版本号递增，稳定性分数也递增
     */
    public List<Map.Entry<String, Integer>> findStableUpgradePath() {
        if (versions.isEmpty()) {
            return new ArrayList<>();
        }
        
        // 按版本号排序
        versions.sort(Map.Entry.comparingByKey());
        
        // 提取稳定性分数
        List<Integer> scores = new ArrayList<>();
        for (Map.Entry<String, Integer> version : versions) {
            scores.add(version.getValue());
        }
        
        // 找到最长递增子序列
        int n = scores.size();
        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        
        int maxLength = 1;
        int maxIndex = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (scores.get(j) < scores.get(i) && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                maxIndex = i;
            }
        }
        
        // 重构路径
        List<Map.Entry<String, Integer>> path = new ArrayList<>();
        int current = maxIndex;
        while (current != -1) {
            path.add(versions.get(current));
            current = parent[current];
        }
        
        Collections.reverse(path);
        return path;
    }
    
    // 使用示例
    public static void main(String[] args) {
        VersionControl vc = new VersionControl();
        String[][] versionsData = {
            {"1.0.0", "85"}, {"1.1.0", "82"}, {"1.2.0", "90"},
            {"2.0.0", "75"}, {"2.1.0", "88"}, {"2.2.0", "92"},
            {"3.0.0", "80"}, {"3.1.0", "95"}
        };
        
        for (String[] data : versionsData) {
            vc.addVersion(data[0], Integer.parseInt(data[1]));
        }
        
        List<Map.Entry<String, Integer>> stablePath = vc.findStableUpgradePath();
        System.out.println("稳定升级路径:");
        for (Map.Entry<String, Integer> entry : stablePath) {
            System.out.println("  " + entry.getKey() + " (稳定性: " + entry.getValue() + ")");
        }
    }
}

---

11. 性能分析

11.1 时间复杂度分析

算法	最好情况	平均情况	最坏情况	空间复杂度
暴力递归	O(2^n)	O(2^n)	O(2^n)	O(n)
动态规划	O(n²)	O(n²)	O(n²)	O(n)
二分优化	O(nlogn)	O(nlogn)	O(nlogn)	O(n)

11.2 性能基准测试

import java.util.*;

public class LISBenchmark {
    /**
     * 性能基准测试
     */
    
    public static void benchmarkLISAlgorithms() {
        int[] testSizes = {100, 500, 1000, 2000};
        Random random = new Random();
        
        for (int size : testSizes) {
            // 生成随机测试数据
            int[] nums = new int[size];
            for (int i = 0; i < size; i++) {
                nums[i] = random.nextInt(1000) + 1;
            }
            
            System.out.println("\n测试数组大小: " + size);
            
            // 测试动态规划解法
            long startTime = System.nanoTime();
            int resultDP = LISDP.lengthOfLISDP(nums);
            long dpTime = System.nanoTime() - startTime;
            
            // 测试二分优化解法
            startTime = System.nanoTime();
            int resultBinary = LISBinarySearch.lengthOfLISBinarySearch(nums);
            long binaryTime = System.nanoTime() - startTime;
            
            double dpTimeMs = dpTime / 1_000_000.0;
            double binaryTimeMs = binaryTime / 1_000_000.0;
            
            System.out.printf("动态规划: %d (耗时: %.4fms)%n", resultDP, dpTimeMs);
            System.out.printf("二分优化: %d (耗时: %.4fms)%n", resultBinary, binaryTimeMs);
            System.out.printf("加速比: %.2fx%n", dpTimeMs / binaryTimeMs);
            
            // 验证结果一致性
            if (resultDP != resultBinary) {
                throw new RuntimeException("结果不一致！");
            }
        }
    }
    
    // 运行基准测试
    public static void main(String[] args) {
        benchmarkLISAlgorithms();
    }
}

11.3 内存优化

import java.util.ArrayList;
import java.util.List;

public class LISSpaceOptimized {
    /**
     * 空间优化版本
     * 只需要O(k)空间，其中k是LIS的长度
     */
    public static int lengthOfLISSpaceOptimized(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // 使用更紧凑的数据结构
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            // 使用二分查找
            int left = 0, right = tails.size();
            while (left < right) {
                int mid = (left + right) >>> 1;  // 无符号右移优化
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            if (left == tails.size()) {
                tails.add(num);
            } else {
                tails.set(left, num);
            }
        }
        
        return tails.size();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("空间优化结果: " + lengthOfLISSpaceOptimized(nums)); // 输出: 4
    }
}

---

12. 最佳实践

12.1 算法选择指南

public class LISAlgorithmSelector {
    /**
     * 根据数据特征选择最适合的算法
     */
    public static int chooseLISAlgorithm(int[] nums) {
        if (nums == null) {
            return 0;
        }
        
        int n = nums.length;
        
        if (n <= 0) {
            return 0;
        } else if (n <= 100) {
            // 小数据量，动态规划足够快且易于理解
            return LISDP.lengthOfLISDP(nums);
        } else if (n <= 10000) {
            // 中等数据量，二分优化是最佳选择
            return LISBinarySearch.lengthOfLISBinarySearch(nums);
        } else {
            // 大数据量，考虑并行化或近似算法
            return LISSpaceOptimized.lengthOfLISSpaceOptimized(nums);
        }
    }
    
    // 测试
    public static void main(String[] args) {
        int[] smallArray = {1, 2, 3};
        int[] mediumArray = new int[1000];
        int[] largeArray = new int[20000];
        
        System.out.println("小数组结果: " + chooseLISAlgorithm(smallArray));
        System.out.println("中等数组结果: " + chooseLISAlgorithm(mediumArray));
        System.out.println("大数组结果: " + chooseLISAlgorithm(largeArray));
    }
}

12.2 调试和可视化

import java.util.*;

public class LISVisualizer {
    /**
     * 可视化LIS计算过程
     */
    public static void visualizeLISProcess(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        System.out.println("输入数组: " + Arrays.toString(nums));
        System.out.println("\n动态规划过程:");
        
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        System.out.println("初始状态: dp = " + Arrays.toString(dp));
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    int oldDp = dp[i];
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    if (dp[i] != oldDp) {
                        System.out.printf("更新 dp[%d]: %d -> %d (因为 nums[%d]=%d < nums[%d]=%d)%n",
                                i, oldDp, dp[i], j, nums[j], i, nums[i]);
                    }
                }
            }
            
            System.out.println("第" + i + "轮后: dp = " + Arrays.toString(dp));
        }
        
        int result = Arrays.stream(dp).max().orElse(0);
        System.out.println("\n最终结果: " + result);
        
        // 显示具体序列
        List<Integer> sequence = getLISSequence(nums);
        System.out.println("具体序列: " + sequence);
    }
    
    private static List<Integer> getLISSequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }
        
        int n = nums.length;
        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        
        int maxLength = 1;
        int maxIndex = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                maxIndex = i;
            }
        }
        
        List<Integer> sequence = new ArrayList<>();
        int current = maxIndex;
        while (current != -1) {
            sequence.add(nums[current]);
            current = parent[current];
        }
        
        Collections.reverse(sequence);
        return sequence;
    }
    
    // 测试可视化
    public static void main(String[] args) {
        int[] testNums = {10, 9, 2, 5, 3, 7, 101, 18};
        visualizeLISProcess(testNums);
    }
}

12.3 错误处理和边界情况

public class RobustLIS {
    /**
     * 健壮的LIS实现，处理各种边界情况
     */
    public static int robustLIS(int[] nums) {
        // 输入验证
        if (nums == null) {
            throw new IllegalArgumentException("输入不能为null");
        }
        
        if (nums.length == 0) {
            return 0;
        }
        
        // 处理特殊情况
        if (nums.length == 1) {
            return 1;
        }
        
        // 检查是否已经是递增序列
        boolean isIncreasing = true;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] >= nums[i + 1]) {
                isIncreasing = false;
                break;
            }
        }
        if (isIncreasing) {
            return nums.length;
        }
        
        // 检查是否是递减序列
        boolean isDecreasing = true;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] <= nums[i + 1]) {
                isDecreasing = false;
                break;
            }
        }
        if (isDecreasing) {
            return 1;
        }
        
        // 使用最优算法
        return LISBinarySearch.lengthOfLISBinarySearch(nums);
    }
    
    // 测试健壮性
    public static void main(String[] args) {
        try {
            System.out.println(robustLIS(new int[]{1, 2, 3, 4, 5}));  // 已排序
            System.out.println(robustLIS(new int[]{5, 4, 3, 2, 1}));  // 逆序
            System.out.println(robustLIS(new int[]{1}));              // 单元素
            System.out.println(robustLIS(new int[]{}));               // 空数组
        } catch (Exception e) {
            System.out.println("错误: " + e.getMessage());
        }
    }
}

12.4 测试用例设计

def comprehensive_test():
    """
    全面的测试用例
    """
    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),
        ([1, 2], 2),
        
        # 特殊情况
        ([1, 2, 3, 4, 5], 5),  # 已排序
        ([5, 4, 3, 2, 1], 1),  # 逆序
        ([1, 1, 1, 1], 1),     # 全相等
        
        # 负数测试
        ([-1, -2, -3, 0, 1], 3),
        
        # 大数测试
        ([1000, 999, 998, 1001, 1002], 3),
    ]
    
    lis = LongestIncreasingSubsequence()
    
    for i, (nums, expected) in enumerate(test_cases):
        # 测试所有算法
        dp_result = lis.dp_solution(nums)
        binary_result = lis.binary_search_solution(nums)
        
        print(f"测试用例 {i+1}: {nums}")
        print(f"  期望结果: {expected}")
        print(f"  DP结果: {dp_result}")
        print(f"  二分结果: {binary_result}")
        
        # 验证结果
        assert dp_result == expected, f"DP算法错误: 期望{expected}, 得到{dp_result}"
        assert binary_result == expected, f"二分算法错误: 期望{expected}, 得到{binary_result}"
        assert dp_result == binary_result, "两种算法结果不一致"
        
        print("  ✓ 通过\n")
    
    print("所有测试用例通过！")

# 运行测试
comprehensive_test()

---

总结

最长递增子序列是一个经典的动态规划问题，具有以下特点：

核心要点

1. 多种解法：从O(n²)的动态规划到O(nlogn)的二分优化
2. 实际应用：版本控制、数据分析、生物信息学等领域
3. 扩展性强：衍生出多个相关问题和变种
4. 面试重点：算法思维和优化能力的综合考查

学习建议

1. 循序渐进：先掌握动态规划解法，再学习二分优化
2. 理解本质：重点理解tails数组的含义和不变量
3. 多做练习：通过LeetCode相关题目加深理解
4. 实际应用：尝试在实际项目中应用LIS思想

进阶方向

1. 并行化LIS：研究大数据场景下的并行算法
2. 在线LIS：处理流式数据的在线算法
3. 近似LIS：在精度和效率之间的权衡
4. 多维LIS：扩展到多维空间的递增子序列

通过深入学习最长递增子序列，不仅能掌握一个重要的算法，更能培养动态规划思维和算法优化能力，为解决更复杂的问题打下坚实基础。