leetcode_[python/C++]_300_Longest Increasing Subsequence

題目連結

【題目】

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example

Given [10, 9, 2, 5, 3, 7, 101, 18],

The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

【分析】

這道題最簡單的思路就是O(n)算法，利用動态規劃，建立一個dp數組

然後從前往後索引，對每一個位置i再從索引0到i-1，一旦找到一個比nums[i]小的值，索引為j,則将dp[j]+1與dp[i]比較取大的值

int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),);
        int ans = ;
        for(int i=;i<nums.size();i++){
            for(int j =  ;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i] = max(dp[i],dp[j]+);
                }
            }
            ans = max(ans,dp[i]);
        }
        return  ans;
    }
           

接下來我們來看O(nlog(n))的算法，利用二分查找的方法，在第二個循環中減少時間複雜度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for(int i=;i<nums.size();i++){
            int right = dp.size();
            int left = ;
            while(left<right){
                int mid = left + (right-left)/;
                if(dp[mid]<nums[i]) left = mid + ;
                else right = mid;
            }
            if(right>=dp.size()) dp.push_back(nums[i]);
            else dp[right] = nums[i];
        }
        return dp.size();
    }
};
           

網上有一種用到内置函數lower_bound()的做法，lower_bound（）函數即求得第一個不小于nums[i]的值，跟上面的思想一緻的

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for(int i=;i<nums.size();i++){
            vector<int>::iterator iter = lower_bound(dp.begin(),dp.end(),nums[i]);
            if(iter == dp.end()){
                dp.push_back(nums[i]);
            }
            else *iter = nums[i];
        }
        return dp.size();
    }
};
           

discuss上有這樣寫的：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    vector<int> ans;
    for (int a : nums)
        if (ans.size() ==  || a > ans.back()) ans.push_back(a);
        else *lower_bound(ans.begin(), ans.end(), a) = a;
    return ans.size();
    }
};
           

python：

def lengthOfLIS(self, nums):
    dp = []
    for items in range(nums):
        left,right = ,len(dp)
        while left<right:
            mid = left + (right-left)/
            if(dp[mid]<items):
                left = mid + 
            else:
                right = mid
        if right >= len(dp):
            dp.append(items)
        else:
            dp[right] = items
    return len(dp)
           

根據這個思想改進一下，可以少去每次計算len(dp)的時間，但在leetcode上顯示不出差别的

def lengthOfLIS(self, nums):
    dp = [] * len(nums)
    size = 
    for x in nums:
        i, j = , size
        while i != j:
            m = (i + j) / 
            if dp[m] < x:
                i = m + 
            else:
                j = m
        dp[i] = x
        size = max(i + , size)
    return size