深圳工程交易中心网,关键词排行优化网站,用ssh做的简单网站,zzcms网站开发个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目
1️⃣题目描述
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [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-10^4 nums[i] 10^4
2️⃣题目解析
本题目使用动态规划来解决此问题。
dp[i]表示以第i个元素结尾的最长递增子序列的长度。通过不断更新以每个元素结尾的最长递增子序列的长度最终得到整个数组的最长递增子序列的长度。
对于每个位置i都需要遍历位置i之前的所有元素j0到i-1判断当前元素nums[i]和之前的元素nums[j]的大小关系。
如果nums[i]大于nums[j]说明当前元素可以接在nums[j]构成的递增子序列后面更新dp[i]为dp[j]1表示将当前元素纳入递增子序列中的长度。
3️⃣解题代码
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();vectorint dp(n,1);int ret 1;for(int i 1;i n;i){for(int j 0;j i;j)if(nums[i] nums[j])dp[i] max(dp[j]1,dp[i]);ret max(ret,dp[i]);}return ret;}
};最后就是代码通过啦
