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