300. 最长递增子序列-JZTXT

方法：动态规划

解题思路

状态表示：\(dp[]\)
- 集合：表示以 \(i\) 结尾的所有递增子序列；
- 属性：\(dp[i]\) 表示集合中最长子序列的长度。
状态计算：
- 集合划分：枚举以 \(i\) 结尾的所有递增子序列的其前一个元素可能的下标 [0, i - 1]，将其划分为以 \(i\) 结尾的所有递增子序列中前一个元素是 \(j\)的集合，\(0 <= j <= i - 1, nums[j] < nums[i]\)。
- \(dp[i] = max\{dp[j] + 1, 1\}\)

代码

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

复杂度分析

时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(n)\)。