題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。
子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence

動(dòng)態(tài)規(guī)劃

定義轉(zhuǎn)移矩陣和轉(zhuǎn)移規(guī)則，設(shè)dp[i]是以數(shù)組第i個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度，那么可以找到dp[i]與之前的元素關(guān)系是，如果nums[i]大于nums[j]，j<i，則dp[i] = max{dp[j] + 1}，j < i。復(fù)雜度。
代碼

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);

        for (int i = 0; i < n; i++) {
            if (i == 0) dp[i] = 1;
            else {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = std::max(dp[j] + 1, dp[i]);
                    }
                }
            }
            cout << dp[i];   
        }

        return *std::max_element(dp.begin(), dp.end());

    }
};

貪心+二分

主要思路是直觀的想法是要讓遞增數(shù)組足夠長(zhǎng)，那么需要前面的數(shù)盡量小，去維護(hù)這樣一個(gè)遞增的數(shù)組。通過遍歷給定的整數(shù)數(shù)組，如果當(dāng)前的元素比維護(hù)數(shù)組的元素大，那么肯定可以添加進(jìn)去，如果不是，說明維護(hù)數(shù)組有的元素比當(dāng)前的元素大，需要做一個(gè)替換用當(dāng)前元素覆蓋掉第一個(gè)比它大的元素（這樣做的話后續(xù)遞增序列才有可能更長(zhǎng)，即使并沒有更長(zhǎng)，這個(gè)覆蓋操作也并沒有副作用，當(dāng)然這個(gè)覆蓋操作可能會(huì)讓最終的結(jié)果數(shù)組值并不是最終的遞增序列值），這樣最后得到的維護(hù)數(shù)組長(zhǎng)度即為目標(biāo)長(zhǎng)度，證明可以看問題討論區(qū)，時(shí)間復(fù)雜度

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

    }
};

相關(guān)題目