学会动态规划最长湍流子数组23
目录
动态规划怎么学?
学习一个算法没有捷径,更何况是学习动态规划,
跟我一起刷动态规划算法题,一起学会动态规划!
1. 题目解析
题目链接:978. 最长湍流子数组 - 力扣(LeetCode)
题目说要找出最长的湍流子数组,但是他的题干太长了,而且不止所云,
所以我们直接通过用例来分析什么是湍流子数组,
通过示例一我们知道了,湍流子数组就是一个大一小一个大一个小的子数组,
通过示例二我们知道了,如果数组一直是递增/递减,最长就是 2,
通过示例三我们知道了,如果数组只有一个元素,那么长度就是 1。
2. 算法原理
1. 状态表示
我们还是从 dp [ i ] 来分析,
dp [ i ] 表示以 i 位置为结尾的所有子数组中,最长的湍流子数组的长度。
实际上他一共存在两种情况:
f [ i ] 表示 i 位置为结尾的所有子数组中,上升状态时最长的湍流子数组的长度,
g [ i ] 表示 i 位置为结尾的所有子数组中,下降状态时最长的湍流子数组的长度,
2. 状态转移方程
f [ i ] 分为三种情况:
当 f [ i - 1 ] > f [ i ] ,要想进入上升状态就得重新计算,所以变成 1
当 f [ i - 1 ] < f [ i ] ,下降状态的最长长度就是 g [ i - 1 ] 1
当 f [ i - 1 ] == f [ i ] ,要想进入平缓状态就得重新计算,所以变成 1
g [ i ] 也同样是这三种情况:
当 g [ i - 1 ] > g [ i ] ,上升状态的最长长度就是 f [ i - 1 ] 1
当 g [ i - 1 ] < g [ i ] ,要想进入下降状态就得重新计算,所以变成 1
当 g [ i - 1 ] == g [ i ] ,要想进入平缓状态就得重新计算,所以变成 1
3. 初始化
我们可以把所有位置先初始化成 1 作为初始值
4. 填表顺序
从左往右,两个表一起填。
5. 返回值
返回两个表里面的最大值。
3. 代码编写
-
class Solution {
-
public:
-
int maxTurbulenceSize(vector<int>& arr) {
-
int n = arr.size();
-
vector<int> f(n, 1), g(n, 1);
-
int ans = 1;
-
for(int i = 1; i < n; i ) {
-
if(arr[i - 1] < arr[i]) f[i] = g[i - 1] 1;
-
else if(arr[i - 1] > arr[i]) g[i] = f[i - 1] 1;
-
ans = max(ans, max(f[i], g[i]));
-
}
-
return ans;
-
}
-
};
写在最后:
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhickeka
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信提示登录环境异常是什么意思原因
PHP中文网 04-09 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
微信人名旁边有个图标有什么用
PHP中文网 03-11