C#最长递增子序列（LIS）详解与性能优化（小白也能学会的LIS算法实战指南）

什么是“最长递增子序列”？

给定一个整数数组，例如 [10, 9, 2, 5, 3, 7, 101, 18]，我们要找出其中最长的严格递增子序列（元素顺序不变，但不必连续）。在这个例子中，一个可能的LIS是 [2, 3, 7, 18]，长度为4。

注意：子序列 ≠ 子数组。子序列可以跳过中间元素，只要保持原有顺序即可。

方法一：朴素动态规划（O(n²)）

最直观的方法是使用动态规划。我们定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。

状态转移方程：

dp[i] = max(dp[j] + 1) ，其中 j < i 且 nums[j] < nums[i]

下面是 C# 实现代码：

public static int LengthOfLIS_O_N2(int[] nums){    if (nums == null || nums.Length == 0) return 0;    int n = nums.Length;    int[] dp = new int[n];    Array.Fill(dp, 1); // 每个元素自身构成长度为1的子序列    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 dp.Max();}

这个方法的时间复杂度是 O(n²)，空间复杂度是 O(n)。对于小规模数据足够，但当 n 很大时（比如 10⁵），就会超时。

方法二：二分查找优化（O(n log n)）

为了提升性能，我们可以使用LIS算法优化技巧：维护一个“潜在递增序列”的数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素。

关键思想：越小的末尾元素，越有利于后续扩展更长的子序列。

我们遍历数组，对每个元素使用二分查找找到它在 tails 中的插入位置，并更新该位置的值。

C# 实现如下：

public static int LengthOfLIS_O_NlogN(int[] nums){    if (nums == null || nums.Length == 0) return 0;    List<int> tails = new List<int>();    foreach (int num in nums)    {        // 使用二分查找找到第一个 >= num 的位置        int left = 0, right = tails.Count;        while (left < right)        {            int mid = left + (right - left) / 2;            if (tails[mid] < num)                left = mid + 1;            else                right = mid;        }        // 如果 left == tails.Count，说明 num 比所有元素都大，追加        if (left == tails.Count)        {            tails.Add(num);        }        else        {            tails[left] = num; // 替换，保持最小末尾        }    }    return tails.Count;}

这个版本的时间复杂度降到了 O(n log n)，非常适合处理大规模数据。这也是面试中常考的最长上升子序列C#实现优化方案。

完整测试示例

class Program{    static void Main()    {        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};        Console.WriteLine("LIS 长度 (O(n²)): " + LengthOfLIS_O_N2(nums));      // 输出: 4        Console.WriteLine("LIS 长度 (O(n log n)): " + LengthOfLIS_O_NlogN(nums)); // 输出: 4    }}

总结

通过本文，你已经掌握了：

• 什么是C#最长递增子序列（LIS）问题
• 如何用动态规划实现 O(n²) 解法
• 如何通过二分查找将时间复杂度优化到 O(n log n)
• 完整的最长上升子序列C#实现代码

无论你是准备面试，还是想提升算法能力，掌握LIS算法优化都是必备技能。赶快动手试试吧！