做网站创业怎么样,wordpress商城主题手机版,北京网站建设公司排名,内容营销的重要性目录 0.子序列 vs 子数组1.最长递增子序列1.题目链接2.算法原理详解3.代码实现 2.摆动序列1.题目链接2.题目链接3.代码实现 0.子序列 vs 子数组
子序列#xff1a; 相对顺序是跟源字符串/数组是一致的但是元素和元素之间#xff0c;在源字符串/数组中可以是不连续的一般时间… 目录 0.子序列 vs 子数组1.最长递增子序列1.题目链接2.算法原理详解3.代码实现 2.摆动序列1.题目链接2.题目链接3.代码实现 0.子序列 vs 子数组
子序列 相对顺序是跟源字符串/数组是一致的但是元素和元素之间在源字符串/数组中可以是不连续的一般时间复杂度 O ( 2 n ) O(2^n) O(2n) 子数组 在源字符串/数组中挑出来必须是连续的 子串与子数组是一个意思 一般时间复杂度 O ( N 2 ) O(N^2) O(N2) 子序列其实相当于包含了子数组子序列问题经典解法两层循环 1.最长递增子序列
1.题目链接
最长递增子序列 2.算法原理详解
注意本题思考方式非常有标志性思路 确定状态表示 - dp[i]的含义 以i位置元素为结尾的所有子序列中最长递增子序列的长度 推导状态转移方程 初始化vectorint dp(n, 1) 确定填表顺序从左往右 确定返回值整个dp表里的最大值 3.代码实现
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[j] nums[i]){dp[i] max(dp[i], dp[j] 1);}}ret max(ret, dp[i]);}return ret;
}2.摆动序列
1.题目链接
摆动序列 2.题目链接
思路 确定状态表示 - dp[i]的含义 以i位置元素为结尾的所有子序列中最长的摆动序列的长度本题状态标识还可以继续划分 f[i]以i位置元素为结尾的所有子序列中最后一个位置呈现“上升”趋势的最长的摆动序列的长度g[i]以i位置元素为结尾的所有子序列中最后一个位置呈现“下降”趋势的最长的摆动序列的长度 推导状态转移方程 令j为i前面的任一一个数 初始化vectorint f(n, 1), g(n, 1) 确定填表顺序从左往右两个表一起填 确定返回值两个dp表里的最大值 3.代码实现
int wiggleMaxLength(vectorint nums)
{int n nums.size();vectorint f(n, 1), g(n, 1);int ret 1;for(int i 1; i n; i){for(int j 0; j i; j){if(nums[j] nums[i]){f[i] max(f[i], g[j] 1);}else if(nums[j] nums[i]){g[i] max(g[i], f[j] 1);}}ret max(ret, max(f[i], g[i]));}return ret;
}
