力扣第300题 最长递增子序列 c++ 动态规划题 附Java代码

题目

300. 最长递增子序列

中等

相关标签

数组   二分查找   动态规划

给你一个整数数组 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)) 吗?

思路和解题方法

• if(nums.size()<=1) return nums.size();：特判，如果数组nums长度为0或1，直接返回其长度。
• vector dp(nums.size(), 1);：创建一个大小为nums长度的数组dp，用于存储以nums[i]结尾的最长上升子序列的长度。初始值全部赋为1，因为每个元素本身也可以构成一个长度为1的上升子序列。
• int ans = 0;：初始化最长上升子序列的长度为0。
• for(int i = 1; i < nums.size(); i++)：从第二个元素开始遍历数组nums。
• for(int j = 0; j < i; j++)：在i之前的元素中，找到比nums[i]小的元素。
• if(nums[i] > nums[j])：如果nums[i]大于nums[j]，则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中。
• dp[i] = max(dp[i], dp[j] + 1);：更新以nums[i]结尾的最长上升子序列的长度。当前位置的值为前面比它小的元素中以每个元素结尾的最长上升子序列长度的最大值+1。
• if(ans < dp[i]) ans = dp[i];：更新最长上升子序列的长度。
• return ans;：返回最长上升子序列的长度。

复杂度

        时间复杂度:

                O(n*n)

时间复杂度分析： 代码中使用了两重循环，时间复杂度为O(n^2)。

其中，内层循环每次迭代都会执行常数个操作（比较和更新dp数组），因此时间复杂度为O(1)。

外层循环的迭代次数为n-1，因此时间复杂度为O(n)。

因此，算法的总时间复杂度为O(n^2)。

        空间复杂度

                O(n)

空间复杂度分析： 代码中使用了一个长度为n的dp数组，因此空间复杂度为O(n)。

c++ 代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()<=1) return nums.size();
        
        vector<int> dp(nums.size(), 1); // 创建一个dp数组，用于存储以nums[i]结尾的最长上升子序列的长度，默认初始为1
        
        int ans = 0; // 初始化最长上升子序列的长度为0
        
        for(int i = 1; i < nums.size(); i++) // 遍历数组nums
        {
            for(int j = 0; j < i; j++) // 在i之前的元素中，找到比nums[i]小的元素
            {
                if(nums[i] > nums[j]) // 如果nums[i]大于nums[j]，则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中
                    dp[i] = max(dp[i], dp[j] + 1); // 更新以nums[i]结尾的最长上升子序列的长度
            }
            
            if(ans < dp[i]) // 更新最长上升子序列的长度
                ans = dp[i];
        }
        
        return ans; // 返回最长上升子序列的长度
    }
};

Java代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length]; // 创建一个大小为nums.length的数组dp，用于存储以nums[i]结尾的最长上升子序列的长度，默认初始为1
        int res = 0; // 初始化最长上升子序列的长度为0
        Arrays.fill(dp, 1); // 将dp数组中的元素全部赋值为1
        for (int i = 1; i < dp.length; i++) { // 遍历数组nums，从第二个元素开始
            for (int j = 0; j < i; j++) { // 在i之前的元素中，找到比nums[i]小的元素
                if (nums[i] > nums[j]) { // 如果nums[i]大于nums[j]，则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 更新以nums[i]结尾的最长上升子序列的长度
                }
                res = Math.max(res, dp[i]); // 更新最长上升子序列的长度
            }
        }
        return res; // 返回最长上升子序列的长度
    }
}

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。