題目描述
給你一個(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：文章來源：http://www.zghlxwxcb.cn/news/detail-699083.html
輸入：nums = [7,7,7,7,7,7,7]
輸出：1
提示：文章來源地址http://www.zghlxwxcb.cn/news/detail-699083.html
1 <= nums.length <= 2500-104 <= nums[i] <= 104
解答
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// dp[i] 表示以 nums[i] 為結(jié)尾的最長遞增子序列
if(nums.size() <= 1) return nums.size();
int n = nums.size();
vector<int> dp(n, 1); // 每個(gè)數(shù)自己都為一個(gè)遞增子序列
int res = 0;
for(int i = 1; i < n; ++i)
{
// 求出以 nums[i] 結(jié)尾的最長遞增子序列
for(int j = 0; j < i; j++)
{
if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
}
if(dp[i] > res) res = dp[i];
}
return res;
}
};
到了這里，關(guān)于300. 最長遞增子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
