动态规划
- 思路：
- 假设 dp[i] 为前 i 个元素构成的最长递增子序列的个数，包含 nums[i]；
- 则 dp[i] 构成序列上一个元素 nums[j] 构成最长递增子序列 dp[j]，则 dp[i] = dp[j] + 1；
- 如果动态取 j ∈ [0, i - 1]，则选取其中最长递增子序列值中最大的，其值 + 1 来更新 dp[i] 的值；
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int size = (int)nums.size();
if (size == 0) {
return 0;
}
std::vector<int> dp(size, 0);
for (int i = 0; i < size; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = std::max(dp[i], dp[j] + 1);
}
}
}
return *std::max_element(dp.begin(), dp.end());
}
};文章来源地址https://www.toymoban.com/news/detail-757855.html
文章来源：https://www.toymoban.com/news/detail-757855.html
到了这里，关于力扣300. 最长递增子序列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
