题目

解法：动态规划

思路

动态规划，定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。

该方法的正确性基于最优子结构。对于任意位置 i，若存在 j < i 且 nums[j] < nums[i]，则所有以 j 结尾的递增子序列都可以通过添加 nums[i] 扩展为以 i 结尾的子序列。dp[i] 取所有可扩展情况的最大值，因此必然记录了以 i 结尾的最长递增子序列长度。最终答案取所有 dp[i] 的最大值，因为全局最长递增子序列必然以某个元素结尾。

• Step 1: 初始化 dp 数组，每个元素为 1
• Step 2: 遍历 i 从 0 到 n-1
• Step 3: 对于每个 i，遍历 j 从 0 到 i-1
• Step 4: 若 nums[i] > nums[j]，更新 dp[i] = max(dp[i], dp[j] + 1)
• Step 5: 返回 dp 数组的最大值

复杂度

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n)$

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};