难度: Medium
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104进阶：
O(n log(n)) 吗?运行时间: 3744 ms
内存: 14.8 MB
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
for i in range(len(dp)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
该题解使用动态规划的思路来解决最长递增子序列问题。定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。通过两层循环，外层循环遍历数组中的每个元素，内层循环遍历当前元素之前的所有元素，如果当前元素大于之前的元素，则更新 dp[i] 为 dp[i] 和 dp[j]+1 中的较大值。最后返回 dp 数组中的最大值，即为最长递增子序列的长度。
时间复杂度: O(n^2)
空间复杂度: O(n)
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 定义 dp 数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
dp = [1] * len(nums)
# 外层循环遍历数组中的每个元素
for i in range(len(dp)):
# 内层循环遍历当前元素之前的所有元素
for j in range(i):
# 如果当前元素大于之前的元素，则更新 dp[i] 为 dp[i] 和 dp[j]+1 中的较大值
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
# 返回 dp 数组中的最大值，即为最长递增子序列的长度
return max(dp)
在动态规划中初始化 dp 数组的每个元素为1的原因是每个元素至少可以是其自身的一个递增子序列，即最短的递增子序列的长度是1。这样的初始化确保了在计算过程中，每个元素至少代表了一个以该元素结尾的序列。
内层循环中的条件 `if nums[i] > nums[j]` 用来判断 nums 中的当前元素 nums[i] 是否大于之前的某个元素 nums[j]。如果是，这意味着 nums[i] 可以接在 nums[j] 形成的递增子序列之后，从而可能形成一个更长的递增子序列。这个条件是动态规划解决最长递增子序列问题的关键，确保了只有在递增的情况下才考虑将 nums[i] 添加到子序列中。
如果数组 `nums` 完全逆序，算法的输出将会是 1，因为在逆序的数组中，没有任何两个连续的元素满足递增的条件，因此每个元素都只能形成长度为1的递增子序列。性能方面，算法仍然需要执行两层循环来检查所有可能的元素对，但每次内层循环的条件检查 `if nums[i] > nums[j]` 都将为假，不会执行任何更新操作。因此，尽管输出为最小可能值，算法的时间复杂度仍然是 O(n^2)。