【学会动态规划】最长湍流子数组（23）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】最长湍流子数组（23）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

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

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：978. 最长湍流子数组 - 力扣（LeetCode）

【学会动态规划】最长湍流子数组（23）,学会动态规划,动态规划,算法

题目说要找出最长的湍流子数组，但是他的题干太长了，而且不止所云，

所以我们直接通过用例来分析什么是湍流子数组，

通过示例一我们知道了，湍流子数组就是一个大一小一个大一个小的子数组，

通过示例二我们知道了，如果数组一直是递增/递减，最长就是 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;
    }
};