当前位置: 首页 > news >正文

【学会动态规划】最长湍流子数组(23)

目录

动态规划怎么学?

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后:


动态规划怎么学?

学习一个算法没有捷径,更何况是学习动态规划,

跟我一起刷动态规划算法题,一起学会动态规划!

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;}
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

http://www.lryc.cn/news/129254.html

相关文章:

  • 【网络编程·网络层】IP协议
  • HTML详解连载(7)
  • 一文打通redis中的String类型
  • 优测云服务平台|【压力测试功能升级】轻松完成压测任务
  • UseEffect中使用setState更新后获取的值为何依然是更新前
  • 去掉鼠标系列之一: 语雀快捷键使用指南
  • 【Linux】Reactor模式
  • 【LeetCode 算法】Merge Two Binary Trees 合并二叉树
  • 系统架构设计师---2017年下午试题1分析与解答(试题五)
  • el-table实现静态和动态合并单元格 以及内容显示的问题
  • STM32F40X系列FSMC8路驱动LCD显示屏(LY-TFT30-39P-1509 芯片hx8352)
  • 小象课堂在线授课教育系统
  • Android 电池容量获取
  • 无涯教程-Perl - tell函数
  • 【论文综述】Transformer 综述
  • 博客摘录「 佛祖保佑,永无bug——springboot启动图案的修改方法」2023年6月8日
  • 【JavaEE进阶】SpringBoot 日志
  • conda - 调研介绍
  • keepalived集群
  • CentOS系统环境搭建(八)——CentOS7开机自动执行脚本(以MySQL为例)
  • re学习(31)BUUCTF-xx(多层加密)
  • HDFS的小文件影响及解决办法
  • 【前端】husky 的使用
  • Spring系列篇 -- Bean的生命周期
  • 分类预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元多输入分类预测
  • Linux权限系列--给普通用户添加某个命令的sudo权限
  • 11-数据结构-栈和队列的应用(C语言)
  • uni-app自定义多环境配置,动态修改appid
  • 04 - 分离头指针情况、理解HEAD和branch
  • C#__基本特性和使用