一、问题描述

给定一个整数数组 nums，返回这个数组的最长递增子序列的长度。

二、方案一：动态规划

1、思路

设计思路：使用动态规划，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

• 初始化 dp 数组，每个位置为 1，因为每个数字本身就是一个长度为 1 的递增子序列。
• 遍历数组，对于每个 nums[i]，再遍历 j 从 0 到 i-1，如果 nums[i] > nums[j]，则更新 dp[i] 为 max(dp[i], dp[j] + 1)。

2、代码实现

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = 1
    }
    maxLen := 1
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
        maxLen = max(maxLen, dp[i])
    }
    return maxLen
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(n)，需要额外的一个数组 dp 来存储每个位置的最长递增子序列的长度。

三、方案二：贪心 + 二分查找

1、思路

设计思路：使用贪心算法和二分查找，维护一个数组 tails，其中 tails[i] 存储长度为 i+1 的所有递增子序列的最小结尾元素。

• 遍历数组 nums，对于每个元素 x，如果它大于 tails 中的所有元素，则将其添加到 tails 的末尾；否则，用它替换掉 tails 中第一个大于或等于它的元素。
• 最后 tails 的长度即为所求的最长递增子序列的长度。

2、代码实现

func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        i, j := 0, len(tails)
        for i < j {
            m := (i + j) / 2
            if tails[m] < x {
                i = m + 1
            } else {
                j = m
            }
        }
        if i == len(tails) {
            tails = append(tails, x)
        } else {
            tails[i] = x
        }
    }
    return len(tails)
}

3、复杂度分析

• 时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(n)，需要额外的一个数组 tails 来存储每个长度的递增子序列的最小结尾元素。

四、总结

方案	时间复杂度	空间复杂度	说明
方案一	O(n^2)	O(n)	动态规划
方案二	O(nlogn)	O(n)	贪心算法 + 二分查找

方案二在时间复杂度上优于方案一，但在空间复杂度上两者相同。在实际应用中，可以根据具体需求选择合适的方案。