最长递增子序列详解（Go语言实现LIS算法从入门到精通）

方法一：动态规划（O(n²) 时间复杂度）

这是最直观的解法。我们定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。

状态转移方程：

dp[i] = max(dp[j] + 1)  对所有 j < i 且 nums[j] < nums[i]初始值：dp[i] = 1 （每个元素自身构成长度为1的子序列）

下面是完整的 Go语言最长递增子序列 实现代码：

package mainimport "fmt"// lengthOfLIS 使用动态规划求最长递增子序列长度func lengthOfLIS(nums []int) int {    if len(nums) == 0 {        return 0    }        n := len(nums)    dp := make([]int, n)        // 初始化：每个位置至少可以构成长度为1的子序列    for i := 0; i < n; i++ {        dp[i] = 1    }        // 动态规划填表    for i := 1; i < n; i++ {        for j := 0; j < i; j++ {            if nums[j] < nums[i] {                if dp[j]+1 > dp[i] {                    dp[i] = dp[j] + 1                }            }        }    }        // 找出dp数组中的最大值    maxLen := dp[0]    for _, val := range dp {        if val > maxLen {            maxLen = val        }    }        return maxLen}func main() {    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}    fmt.Println("最长递增子序列长度:", lengthOfLIS(nums)) // 输出: 4}

方法二：贪心 + 二分查找（O(n log n) 时间复杂度）

对于大规模数据，O(n²) 的解法可能不够高效。我们可以使用更优的 贪心策略结合二分查找 来优化到 O(n log n)。

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

遍历原数组，对每个元素：

• 如果比 tails 最后一个元素大，直接追加；
• 否则，用二分查找找到第一个 ≥ 当前元素的位置，替换它。

最终 tails 的长度就是 LIS 的长度。

package mainimport (    "fmt"    "sort")// lengthOfLISOptimized 使用贪心+二分查找求LIS长度func lengthOfLISOptimized(nums []int) int {    tails := []int{}        for _, num := range nums {        // 使用二分查找找到插入位置        pos := sort.SearchInts(tails, num)                if pos == len(tails) {            // 如果num比所有元素都大，追加到末尾            tails = append(tails, num)        } else {            // 否则替换第一个≥num的元素            tails[pos] = num        }    }        return len(tails)}func main() {    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}    fmt.Println("最长递增子序列长度 (优化版):", lengthOfLISOptimized(nums)) // 输出: 4}

为什么这个方法有效？

虽然 tails 数组本身不一定是真实的 LIS，但它正确地维护了“长度为 k 的递增子序列的最小尾部”这一信息。这保证了后续有更大的可能性扩展出更长的子序列，从而得到正确的长度。

总结

通过本教程，你已经掌握了两种实现 LIS算法 的方法：

• 基础版：动态规划，易于理解，适合学习；
• 进阶版：贪心 + 二分查找，效率更高，适合面试和实战。

无论你是准备面试，还是想提升 Go语言算法教程 的实战能力，LIS 都是一个值得深入理解的经典问题。动手敲一遍代码，你会收获更多！

关键词回顾：Go语言最长递增子序列、LIS算法、动态规划Go实现、Go语言算法教程。