最大递增子序列

最大递增子序列是一个经典的问题，即在一个给定的序列中，找到一个最长的子序列，使得子序列中的元素按照升序排列。以下是一个常见的动态规划算法实现：

假设给定序列为 nums，长度为 n。

1. 定义状态

设 dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。

2. 定义状态转移方程

对于状态 dp[i]，需要找到前面的所有状态 dp[j]（0 <= j < i），满足 nums[j] < nums[i]，并选取其中最大的 dp[j]，然后在其基础上加上当前元素 nums[i]，即可得到当前状态 dp[i] 的值。

因此，状态转移方程为：

dp[i] = max(dp[j]) + 1, 其中 0 <= j < i, nums[j] < nums[i]

3. 定义初始状态

初始状态为 dp[i] = 1，因为以 nums[i] 为结尾的最长递增子序列至少包含 nums[i] 这个元素。

4. 求解最优解

最终的最长递增子序列的长度为 dp 数组中的最大值，即 max(dp[i])，其中 0 <= i < n。

以下是一个基于动态规划的 Python 代码实现：

def lengthOfLIS(nums):
    n = len(nums)
    if n == 0:
        return 0
    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)

时间复杂度为 O(n^2)，可以通过一些优化方法将其优化至 O(nlogn)。