leetcode第300题：最长上升子序列 [否]

题目描述

image.png

考点

• 二分查找
• 动态规划

解题思路

• 状态定义：dp[i]表示以nums[i]结尾的，最长上升子序列的长度；
• 状态转移方程：dp[i] = max{dp[0]+1, dp[1]+1, ..., dp[i-1]+1}, 如果dp[i] > dp[i-1]；

解题思路.png

代码实现

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() <= 1)
            return nums.size();
            
        int res = 1;
        // dp[i]: 表示以nums[i]结尾的，最长上升子序列的长度；
        vector<int> dp(nums.size(), 1);

        for(int i = 1; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
            }

            res = max(res, dp[i]);            
        }

        return res;
    }
};