最长递增子序列：动态规划和贪心算法详解

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

输入：10 9 2 5 3 7 101 18 输出：4

解法一：动态规划

动态规划的思路是，维护一个数组 dp，其中 dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。

对于每一个数字 nums[i]，从第一个数字开始遍历到 i，如果发现某个数字 nums[j] 小于 nums[i]，则更新 dp[i]，即：

dp[i] = max(dp[i], dp[j] + 1)

最后，dp 数组中的最大值即为所求。

时间复杂度：O(n^2)

Python 代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        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)

解法二：贪心 + 二分查找

我们可以维护一个数组 tail，其中 tail[i] 表示长度为 i 的最长上升子序列的结尾数字。遍历原始数组 nums，如果当前数字 nums[i] 大于 tail 数组的最后一个元素，说明 nums[i] 可以接在最长上升子序列的后面，长度加一；否则，我们在 tail 数组中找到第一个大于等于 nums[i] 的数字，将其替换为 nums[i]。因为这样可以保证 tail 数组中的每个元素都是最小的，从而使得长度为 i 的最长上升子序列的结尾数字最小。

最后，tail 数组的长度即为所求。

时间复杂度：O(nlogn)

Python 代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        tail = [0] * n
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                mid = (i + j) // 2
                if tail[mid] < x:
                    i = mid + 1
                else:
                    j = mid
            tail[i] = x
            size = max(size, i + 1)
        return size

总结

动态规划方法较为直观，易于理解，但时间复杂度较高。贪心 + 二分查找方法利用了贪心策略，在效率上有所提升，但实现起来略微复杂。选择哪种方法取决于具体的需求和场景。