C++ LeetCode300最長遞增子序列

更新時(shí)間：2022年12月16日 11:41:48 作者：LetMeFly

這篇文章主要為大家介紹了C++ LeetCode300最長遞增子序列示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

LeetCode 300.最長遞增子序列

力扣題目鏈接：leetcode.cn/problems/lo…

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

子序列 是由數(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
-104 <= nums[i] <= 104

進(jìn)階：

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

方法一：動(dòng)態(tài)規(guī)劃

AC代碼

C++

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[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

以上就是C++ LeetCode300最長遞增子序列的詳細(xì)內(nèi)容，更多關(guān)于C++ 最長遞增子序列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

一文快速掌握C++雙端數(shù)組容器deque的使用
本文和大家分享的是和vector容器功能很像的容器——deque，了解deque容器的本質(zhì)，使用方法以及與vector容器的不同之處，感興趣的快跟隨小編一起學(xué)習(xí)學(xué)習(xí)吧
2022-07-07
OpenGL實(shí)現(xiàn)鼠標(biāo)移動(dòng)方塊
這篇文章主要為大家詳細(xì)介紹了OpenGL實(shí)現(xiàn)鼠標(biāo)移動(dòng)方塊，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-08-08
C語言連續(xù)生成多個(gè)隨機(jī)數(shù)實(shí)現(xiàn)可限制范圍
這篇文章主要介紹了C語言連續(xù)生成多個(gè)隨機(jī)數(shù)實(shí)現(xiàn)可限制范圍，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-01-01
C++實(shí)現(xiàn)猜數(shù)字小游戲
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)猜數(shù)字小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-10-10
C++結(jié)構(gòu)體數(shù)組詳細(xì)解析
定義結(jié)構(gòu)體數(shù)組和定義結(jié)構(gòu)體變量類似，定義結(jié)構(gòu)體數(shù)組時(shí)只需聲明其為數(shù)組即可
2013-10-10
zlib庫壓縮和解壓字符串STL string的實(shí)例詳解
這篇文章主要介紹了zlib庫壓縮和解壓字符串STL string的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家，需要的朋友可以參考下
2017-10-10
C++實(shí)現(xiàn)線性表有序表的合并方式(順序表實(shí)現(xiàn)and鏈表實(shí)現(xiàn))
這篇文章主要介紹了C++實(shí)現(xiàn)線性表有序表的合并方式(順序表實(shí)現(xiàn)and鏈表實(shí)現(xiàn)),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2024-04-04
C語言中多維數(shù)組的內(nèi)存分配和釋放(malloc與free)的方法
寫代碼的時(shí)候會(huì)碰到多維數(shù)組的內(nèi)存分配和釋放問題，在分配和釋放過程中很容易出現(xiàn)錯(cuò)誤。下面貼上一些示例代碼，以供參考。
2013-05-05
C語言數(shù)據(jù)結(jié)構(gòu)之學(xué)生信息管理系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語言數(shù)據(jù)結(jié)構(gòu)之學(xué)生信息管理系統(tǒng)課程設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2017-11-11
c++模擬實(shí)現(xiàn)string類詳情
這篇文章主要介紹了c++模擬實(shí)現(xiàn)string類詳情，string表示可變長的字符序列，使用string類型必須首先包含string頭文件。作為標(biāo)準(zhǔn)庫的一部分，string定義在命名空間std中，下面進(jìn)入文章一起看看詳細(xì)內(nèi)容吧
2022-01-01