C++ LeetCode300最長遞增子序列
更新時間：2022年12月16日 11:41:48 作者：LetMeFly
這篇文章主要為大家介紹了C++ LeetCode300最長遞增子序列示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
LeetCode 300.最長遞增子序列
力扣題目鏈接：leetcode.cn/problems/lo…
給你一個整數(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
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
進階：
- 你能將算法的時間復雜度降低到
O(n log(n))嗎?
方法一：動態(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最長遞增子序列的詳細內(nèi)容，更多關于C++ 最長遞增子序列的資料請關注腳本之家其它相關文章！
您可能感興趣的文章:
相關文章
本文和大家分享的是和vector容器功能很像的容器——deque，了解deque容器的本質(zhì)，使用方法以及與vector容器的不同之處，感興趣的快跟隨小編一起學習學習吧2022-07-07
這篇文章主要為大家詳細介紹了OpenGL實現(xiàn)鼠標移動方塊，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
C語言連續(xù)生成多個隨機數(shù)實現(xiàn)可限制范圍
這篇文章主要介紹了C語言連續(xù)生成多個隨機數(shù)實現(xiàn)可限制范圍，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
這篇文章主要為大家詳細介紹了C++實現(xiàn)猜數(shù)字小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-10-10
定義結構體數(shù)組和定義結構體變量類似，定義結構體數(shù)組時只需聲明其為數(shù)組即可2013-10-10
這篇文章主要介紹了zlib庫壓縮和解壓字符串STL string的實例詳解的相關資料,希望通過本文能幫助到大家，需要的朋友可以參考下2017-10-10
C++實現(xiàn)線性表有序表的合并方式(順序表實現(xiàn)and鏈表實現(xiàn))
這篇文章主要介紹了C++實現(xiàn)線性表有序表的合并方式(順序表實現(xiàn)and鏈表實現(xiàn)),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-04-04
C語言中多維數(shù)組的內(nèi)存分配和釋放(malloc與free)的方法
寫代碼的時候會碰到多維數(shù)組的內(nèi)存分配和釋放問題，在分配和釋放過程中很容易出現(xiàn)錯誤。下面貼上一些示例代碼，以供參考。2013-05-05
C語言數(shù)據(jù)結構之學生信息管理系統(tǒng)課程設計
這篇文章主要為大家詳細介紹了C語言數(shù)據(jù)結構之學生信息管理系統(tǒng)課程設計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-11-11
這篇文章主要介紹了c++模擬實現(xiàn)string類詳情，string表示可變長的字符序列，使用string類型必須首先包含string頭文件。作為標準庫的一部分，string定義在命名空間std中，下面進入文章一起看看詳細內(nèi)容吧2022-01-01