线性dp求最长递增子序列

最长递增子序列问题是一个经典的动态规划问题可以使用线性动态规划来解决。

定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。初始时，将 dp 数组的所有元素初始化为 1。

然后，对于每个元素 nums[i]，需要遍历从 0 到 i-1 的所有元素 nums[j]，如果 nums[i] 大于 nums[j]，则可以将 nums[i] 加入到以 nums[j] 结尾的最长递增子序列中，从而得到新的长度 dp[i] = dp[j] + 1。在遍历过程中，不断更新 dp[i] 的最大值。

最后，遍历整个 dp 数组，找到最大的长度即为最长递增子序列的长度。

下面是一个示例代码实现：

def lengthOfLIS(nums):
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

这个算法的时间复杂度是 O(n^2)，其中 n 是输入数组的长度。可以通过优化到 O(nlogn) 的时间复杂度，但需要使用二分搜索来实现。