求最长递增子序列

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是指在一个序列中，找到一个最长的子序列使得这个子序列中的元素是递增的。

求最长递增子序列有多种算法，其中比较常见的是动态规划算法。具体实现方法如下：

1. 定义状态：dp[i] 表示以第 i 个元素为结尾的最长递增子序列的长度。

2. 初始化状态：dp[i] 的初始值为 1，因为最短的递增子序列只包含一个元素。

3. 状态转移：对于每个 i，从 0 到 i-1 遍历 j，如果 nums[i] 大于 nums[j]，则 dp[i] = max(dp[i], dp[j]+1)。

4. 最终结果：遍历 dp 数组，取最大值即为最长递增子序列的长度。

以下是 Python 代码实现：

def lengthOfLIS(nums):
    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)，还有一些时间复杂度更优秀的算法，比如利用二分查找的算法，时间复杂度为 O(nlogn)。