Leetcode 300 - Longest Increasing Subsequence

題目

Problem#

給你一個陣列，回傳其最長嚴格遞增子序列(LIS)。

測資限制#

• $1 \le n \le 2500$

想法#

LIS 裸題

https://web.ntnu.edu.tw/~algo/Subsequence.html

AC Code#

Copy

class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> v;
        v.push_back(nums[0]);
 
        for(int i = 1; i < n; i++)
        {
            if(v.back() < nums[i])
            {
                v.push_back(nums[i]);
            }
            else
            {
                auto it = lower_bound(v.begin(), v.end(), nums[i]);
                *it = nums[i];
            }
        }
        return v.size();
    }
};

view raw leetcode/300.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n\log{n})$
• 空間複雜度: $\mathcal{O}(n)$

心得#

太久沒寫都忘了 QQ