LeetCode 300. 最长递增子序列

LeetCode 300. 最长递增子序列

动态规划

const int N = 2510;
class Solution {
public:
    int f[N];
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for(int i = 0; i < n; i ++)
        {
            f[i] = 1;
            for(int j = 0; j < i; j ++)
                if(nums[i] > nums[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        return res;
    }
};

DP + 二分

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        vector<int> f;
        for(auto &n : nums)
        {
            auto idx = lower_bound(f.begin(), f.end(), n) - f.begin(); //找到大于等于 n 的位置
            if(idx >= f.size()) //如果不存在
                f.push_back(n);
            else
                f[idx] =  min(f[idx], n); //存在贪心取最小
        }
        return f.size();
    }
};