300. Longest Increasing Subsequence

Hint

class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        // Initialize a dp vector where dp[i] represents the length of the longest
        // increasing subsequence that ends with nums[i]
        vector<int> dp(n, 1);
        
        // Iterate through each element of nums starting from the second element
        for ()
        {
            // For each element nums[i], check all previous elements nums[j]
            // to find if there is a valid increasing subsequence
            for ()
            {
                // If nums[j] is smaller than nums[i], we can extend the
                // subsequence ending at nums[j] to include nums[i]
                if ()
                {
                    // Update dp[i] to be the maximum of its current value
                    // or dp[j] + 1 (which represents extending the subsequence)
                }
            }
        }
        // The length of the longest increasing subsequence is the maximum value
        // in the dp vector
    }
};

Solution - DP

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

• T:
  $O(N^2)$
• S:
  $O(N)$

Solution - Use lower_bound

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (nums.empty()) return 0;
        vector<int> res;
        
        // 將數列的第一個放到 res
        res.push_back(nums[0]);
        for (int i = 1; i < n; i++) {
            // 跟 res 的最後一個數字作比較
            // 如果 nums[i] 比較大的話，代表是遞增數列
            // 將目前的數字 nums[i] 推到 res
            if (nums[i] > res.back()) {
                res.push_back(nums[i]);
            } else {
                // 如果 nums[i] 比較小的話
                // 找到數列中，大於等於 nums[i] 的位置 j
                // 並且將原本位置 j 的數字，取代成 nums[i]
                // 因為 nums[i] 比較小，我們需要維持 res 是一個遞增數列
                int j = lower_bound(res.begin(), res.end(), nums[i]) - res.begin();
                res[j] = nums[i];
            }
        }
        return res.size();
    }
};

• T:
  $O(N\cdot \log N)$
• S:
  $O(N)$