力扣300. 最长递增子序列（动态规划）

Problem: 300. 最长递增子序列

文章目录

• 题目描述
• 思路
• 解题方法
• 复杂度
• Code

题目描述

思路

1.状态定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
2.状态初始化：dp[0] = 1(因为初始时nums[0]作为一个子序列长度为1)；
3.如果在遍历到下标j时（j < i）若nums[i] > nums[j]则dp[i] = max(dp[i], dp[j] + 1)😭)

解题方法

1.获取数组nums的大小为n；定义int类型数组dp记录以nums[i]为结尾的序列的最大长度；
2.初始化dp[0]为1表示起始递增子序列长度为1；
3.从dp数组下标为1处开始遍历，外层循环从1_{n；内存循环从1}i；每次在外层循环中将dp[i]置为1，表示从当前位置开始递增子序列长度为1，内存循环中若*nums[j] < nums[i]*则dp[i] = max(dp[i], dp[j] + 1)
4.返回dp数组中的最大值

复杂度

时间复杂度:

;其中表示数组nums的大小

空间复杂度:

Code

class Solution {
public:
    /**
     *Dynamic programming finds the longest increasing subsequence
     * @param nums Given array(The sequence to be found)
     * @return int
     */
    int lengthOfLIS(vector<int> &nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = 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);
                }
            }
        }
        int result = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }
};