• https://leetcode.cn/problems/longest-increasing-subsequence/

• 給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴格遞增子序列的長度。

• 子序列 是由數(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

LIS即最長上升子序列，指的是給定一個數(shù)列，從中選取一個子序列，使得子序列中的所有元素單調(diào)遞增，并且滿足子序列的長度最長。以下是LIS的動態(tài)規(guī)劃代碼實現(xiàn)（時間復(fù)雜度為 $O(n^2)$）：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) {
        return n;
    }
    vector<int> dp(n, 1);
    int max_len = dp[0];
    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);
            }
        }
        max_len = max(max_len, dp[i]);
    }
    return max_len;
}

其中，$dp[i]$ 表示以第 $i$ 個元素為結(jié)尾的最長上升子序列的長度。狀態(tài)轉(zhuǎn)移方程為：

d p [ i ] = max ? j = 0 i ? 1 { d p [ j ] + 1 } , if ? n u m s [ i ] > n u m s [ j ] dp[i]=\max_{j=0}^{i-1} \{dp[j]+1\},\quad \text{if}\, nums[i] > nums[j] dp[i]=j=0maxi?1?{dp[j]+1},ifnums[i]>nums[j]

其中，$nums$ 表示原數(shù)列。

代碼中，使用雙重循環(huán)來計算 $dp$ 數(shù)組。外層循環(huán)遍歷所有元素，內(nèi)層循環(huán)遍歷當前元素前面的所有元素，如果存在一個元素小于當前元素，那么就可以將當前元素添加進該元素為結(jié)尾的最長上升子序列中，從而得到以當前元素為結(jié)尾的最長上升子序列。

循環(huán)結(jié)束后，$dp$ 數(shù)組中的最大值即為整個數(shù)列的最長上升子序列長度。

需要注意的是，以上代碼中沒有考慮數(shù)列中存在相同元素的情況。如果數(shù)列中存在相同元素，那么在轉(zhuǎn)移時應(yīng)該將條件 $nums[i]>nums[j]$ 改為 $nums[i]>nums[j]\text{and}dp[i]\le dp[j]$，保證子序列的單調(diào)性和最長性質(zhì)。文章來源地址http://www.zghlxwxcb.cn/news/detail-620498.html

題解

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    //動態(tài)規(guī)劃 dp[i]為到i位置的最長嚴格遞增子序列，結(jié)果輸出dp[n-1]
    vector<int> dp(nums.size(),1);//最小值為1
    for(int i=1;i<dp.size();i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j])
                dp[i] =max(dp[i],dp[j]+1);
        }
    }
    int res = 0;
    for(int i=0;i<dp.size();i++){
        cout<< dp[i]<<",";
        res = max(dp[i],res);
    }
    return res;
    }
};

錯解

#include <stdio.h>
#include<vector>
#include<memory>
#include<iostream>
#include<algorithm>
using namespace std;
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    //動態(tài)規(guī)劃 dp[i]為到i位置的最長嚴格遞增子序列，結(jié)果輸出dp[n-1]
    vector<int> dp(nums.size(),1);//最小值為1
    for(int i=1;i<dp.size();i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j])
                dp[i] =max(dp[i],dp[j]+1);
            else
                 dp[i] = 1;//前邊沒有更小的值了  應(yīng)該去掉這個else部分
        }
    }
    int res = 0;
    for(int i=0;i<dp.size();i++){
        cout<< dp[i]<<",";
        res = max(dp[i],res);
    }
    return res;
    }
};

int main()
{

    vector<int> arr = {7,7,7,7,7,7,7};//{10,9,2,5,3,7,101,18};

    unique_ptr<Solution> mysolo = unique_ptr<Solution>(new Solution());
    int res = mysolo->lengthOfLIS(arr);
    cout<<res<<endl;
    return 0;
}

到了這里，關(guān)于leetcode300. 最長遞增子序列 子序列（不連續(xù)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！