C语言重构【300】最长递增子序列 分手后的思念是犯贱 2023-01-07 10:10 165阅读 0赞 ### 文章目录 ### * * * * 所有题目源代码:\[Git地址\](https://github.com/ch98road/leetcode) * 题目 * 方案: * * 复杂度计算 #### 所有题目源代码:[Git地址][Git] #### #### 题目 #### 给你一个整数数组 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 #### 方案: #### * 二维dp,思路如下灵魂图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70] class Solution { public: int lengthOfLIS(vector<int> &nums) { //当前递增数now、最大递增数res int len = nums.size(); if (len == 0) return 0; int res = 1; vector<vector<int>> dp(len, vector<int>(len, 1)); for (int i = 1; i < len; i++) { dp[i][0] = nums[i]>nums[0]?2:1; for (int j = 1; j <= i; j++) { if (nums[i] > nums[j]) dp[i][j] = max(dp[j][j]+1, dp[i][j - 1]); else dp[i][j] = dp[i][j - 1]; } res = max(res,dp[i][i]); } return res; } }; ##### 复杂度计算 ##### * 时间复杂度:O(n2) * 空间复杂度:O(n2) [Git]: https://github.com/ch98road/leetcode [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: /images/20221119/7bb49bd502ad4d41acd2d9d561e7af5b.png
还没有评论,来说两句吧...