最长递增子序列（LeetCode 300）
一、题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
二、题目解析
三、参考代码
1、Java 代码
class Solution {
public int lengthOfLIS(int[] nums) {
// 设置数组 dp，用来存储 nums 中以每个元素结尾的最长递增序列的程度
// dp[0] 表示以 nums[0] 结尾的最长递增序列的长度
// dp[1] 表示以 nums[1] 结尾的最长递增序列的长度
// dp[i] 表示以 nums[i] 结尾的最长递增序列的长度
int[] dp = new int[nums.length];
// 首先将数组 dp 里面的值都初始化为 1
// 1 表示以当前元素结尾的最长递增序列的长度为 1
// 即最长递增序列就是当前元素本身
Arrays.fill(dp, 1);
// 设置一个变量用来存储最长递增序列的结果
int maxLength = 1;
// 从 1 开始，直到 dp.length ，往 dp 里面填充结果
for(int i = 1 ; i < dp.length ; i++){
// 对于 dp[i] 来说，在 nums 中从 0 到 i - 1 都是在 i 的前面的
// 比如 nums 为 [1,5,2,5,3,7,2]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 从 0 遍历到 i - 1，就可以从这些数字中选出小于 i 的数字
for(int j = 0; j < i ;j++){
// 索引 0 1 2 3 4 5 6
// nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 1、从这些数字中选出小于 nums[i] 的数字
// 2、小于 nums[i] 的那些数字是 1 , 2 ，在之前都已经计算过以 1 或者 2 结尾的最长递增序列的长度
// 并且这个结果存放在 dp[j] 中
// 如果数字为 1，那么此时 j 为 0，dp[0] 存放了以 1 结尾的最长递增序列的长度
// 如果数字为 2，那么此时 j 为 2，dp[2] 存放了以 2 结尾的最长递增序列的长度
// 3、如果发现此时 dp[i] 小于了 dp[j] + 1
// 4、说明此时 dp[i] 中的值就不是以 nums[i] 结尾的最长递增序列的长度
// 需要更新 dp[i]
if(nums[i] > nums[j] && dp[i] < dp[j] + 1){
// 4、更新 dp[i]
dp[i] = dp[j] + 1;
}
}
// 在更新 dp[i] 的过程中，发现了一个更长的子序列
if(maxLength < dp[i]){
// 那么把更长的子序列的长度赋值给 maxLength
maxLength = dp[i];
}
}
// 最后返回 maxLength 就行
return maxLength;
}
}
2、C++ 代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// 设置数组 dp，用来存储 nums 中以每个元素结尾的最长递增序列的程度
// dp[0] 表示以 nums[0] 结尾的最长递增序列的长度
// dp[1] 表示以 nums[1] 结尾的最长递增序列的长度
// dp[i] 表示以 nums[i] 结尾的最长递增序列的长度
// 首先将数组 dp 里面的值都初始化为 1
// 1 表示以当前元素结尾的最长递增序列的长度为 1
// 即最长递增序列就是当前元素本身
vector<int> dp(nums.size(),1);
// 设置一个变量用来存储最长递增序列的结果
int maxLength = 1;
// 从 1 开始，直到 dp.length ，往 dp 里面填充结果
for(int i = 1 ; i < dp.size() ; i++){
// 对于 dp[i] 来说，在 nums 中从 0 到 i - 1 都是在 i 的前面的
// 比如 nums 为 [1,5,2,5,3,7,2]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 从 0 遍历到 i - 1，就可以从这些数字中选出小于 i 的数字
for(int j = 0; j < i ;j++){
// 索引 0 1 2 3 4 5 6
// nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 1、从这些数字中选出小于 nums[i] 的数字
// 2、小于 nums[i] 的那些数字是 1 , 2 ，在之前都已经计算过以 1 或者 2 结尾的最长递增序列的长度
// 并且这个结果存放在 dp[j] 中
// 如果数字为 1，那么此时 j 为 0，dp[0] 存放了以 1 结尾的最长递增序列的长度
// 如果数字为 2，那么此时 j 为 2，dp[2] 存放了以 2 结尾的最长递增序列的长度
// 3、如果发现此时 dp[i] 小于了 dp[j] + 1
// 4、说明此时 dp[i] 中的值就不是以 nums[i] 结尾的最长递增序列的长度
// 需要更新 dp[i]
if(nums[i] > nums[j] && dp[i] < dp[j] + 1){
// 4、更新 dp[i]
dp[i] = dp[j] + 1;
}
}
// 在更新 dp[i] 的过程中，发现了一个更长的子序列
if(maxLength < dp[i]){
// 那么把更长的子序列的长度赋值给 maxLength
maxLength = dp[i];
}
}
// 最后返回 maxLength 就行
return maxLength;
}
};
3、Python 代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 设置数组 dp，用来存储 nums 中以每个元素结尾的最长递增序列的程度
# dp[0] 表示以 nums[0] 结尾的最长递增序列的长度
# dp[1] 表示以 nums[1] 结尾的最长递增序列的长度
# dp[i] 表示以 nums[i] 结尾的最长递增序列的长度
# 首先将数组 dp 里面的值都初始化为 1
# 1 表示以当前元素结尾的最长递增序列的长度为 1
# 即最长递增序列就是当前元素本身
dp = [ 1 for _ in range(len(nums))]
# 设置一个变量用来存储最长递增序列的结果
maxLength = 1
# 从 1 开始，直到 dp.length ，往 dp 里面填充结果
for i in range( 1 , len(dp) ) :
# 对于 dp[i] 来说，在 nums 中从 0 到 i - 1 都是在 i 的前面的
# 比如 nums 为 [1,5,2,5,3,7,2]
# 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
# 从 0 遍历到 i - 1，就可以从这些数字中选出小于 i 的数字
for j in range ( 0 , i ) :
# 索引 0 1 2 3 4 5 6
# nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
# 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
# 1、从这些数字中选出小于 nums[i] 的数字
# 2、小于 nums[i] 的那些数字是 1 , 2 ，在之前都已经计算过以 1 或者 2 结尾的最长递增序列的长度
# 并且这个结果存放在 dp[j] 中
# 如果数字为 1，那么此时 j 为 0，dp[0] 存放了以 1 结尾的最长递增序列的长度
# 如果数字为 2，那么此时 j 为 2，dp[2] 存放了以 2 结尾的最长递增序列的长度
# 3、如果发现此时 dp[i] 小于了 dp[j] + 1
# 4、说明此时 dp[i] 中的值就不是以 nums[i] 结尾的最长递增序列的长度
# 需要更新 dp[i]
if nums[i] > nums[j] and dp[i] < dp[j] + 1 :
# 4、更新 dp[i]
dp[i] = dp[j] + 1
# 在更新 dp[i] 的过程中，发现了一个更长的子序列
if maxLength < dp[i] :
# 那么把更长的子序列的长度赋值给 maxLength
maxLength = dp[i]
# 最后返回 maxLength 就行
return maxLength
