C语言重构【300】最长递增子序列

分手后的思念是犯贱 2023-01-07 10:10 188阅读 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