子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

示例 1：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

示例 2：
輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：
輸入：nums = [7,7,7,7,7,7,7]
輸出：1

提示：

• 1 <= nums.length <= 2500
• $?10^4$ <= nums[i] <= $10^4$

進(jìn)階：

你能將算法的時間復(fù)雜度降低到 $O(nlog(n))$ 嗎?

題解1 DP O ( n 2 ) O(n^{2}) O(n2)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int maxN = INT_MIN;
        /**
        dp[i] : i處數(shù)值對應(yīng)的最長子序列長度
        **/
        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);
            }
            maxN = max(maxN, dp[i]);
        }
        return maxN == INT_MIN ? 1 : maxN;
    }
};

題解2 貪心+二分搜索（ref. from Leetcode） O ( n l o g ( n ) ) O(n log(n)) O(nlog(n))

“從左到右（序列順序），維護(hù)一個每個元素盡可能小的LIS備選集合S”

每個元素盡可能小，這樣更可能在末尾加上一個新的值，構(gòu)成一個更大的LIS

只增加（add）和替換（swap），因此完成遍歷后S的長度一定等于LIS的長度,部分元素可能被你替換掉了，所以在整個遍歷過程中，這個集合S可能并不是LIS本身,盡管如此，LIS的元素一定曾出現(xiàn)在S中（但可能在遍歷過程中被swap覆蓋掉了）

鼓掌??！這個思想好棒

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(1 == nums.size()) return 1;
        // p[i]: 長度為i的最長上升子序列的末尾元素最小值
        vector<int> p(nums.size()+1, 0);
        int len = 1;
        p[len] = nums[0];
        
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > p[len]){
                len ++;
                p[len] = nums[i];
            }else{
                // 在i位置不用遍歷得到dp值
                // 長度=len+1的子序列的最小值 > nums[i]，為了保持p的遞增，需要修改某個位置的值
                // 用二分找到最近的j, 滿足p[j] < nums[i] < p[j+1]
                // s.t. p[j+1] = nums[i];
                // 如果找不到, 說明所有的數(shù)都比 nums[i] 大，此時要更新 d[1]，所以這里將 pos 設(shè)為 0
                int left = 1;
                int right = len;
                int pos = 0;
                // 最希望的是改p[len], 所以判斷條件 有 =
                // 實(shí)際上是想不用遍歷，用二分檢查一遍 nums[i]是不是大于len+1情況里的倒數(shù)第二個最大的數(shù)吧
                while(left <= right){
                    int mid = (left+right) >> 1;
                    // 找到了j
                    if(nums[i] > p[mid]){
                        pos = mid;
                        left = mid+1;
                    }  
                    else{
                        right = mid-1;
                    }
                }
                p[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

文章來源地址http://www.zghlxwxcb.cn/news/detail-724336.html

到了這里，關(guān)于57 最長遞增子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！