动态规划 —— 子数组系列-最长湍流子数组

1. 最长湍流子数组

题目链接：

978. 最长湍流子数组 - 力扣（LeetCode）https://leetcode.cn/problems/longest-turbulent-subarray/description/

2. 题目解析

假如有一个数组{a , b , c , d }如果在a这个位置，b比a大，呈上升趋势，c比b小，呈下降趋势，d比c大，呈上升趋势，像这种就是湍流子数组，简单来说就是必须的是上下上下或者下上下上

像这种一直上升或者一直下降的长度就是2 

如果单单只有一个的话就是1 

3. 算法原理 

状态表示：以某一个位置为结尾或者以某一个位置为起点

  

f[i]表示：以i位置为结尾的所有子数组中，最后一个位置呈上升状态下的最长湍流子数组的长度

  

g[i]表示：以i位置为结尾的所有子数组中，最后一个位置呈下降状态下的最长湍流子数组的长度  

2. 状态转移方程

  

f[i]分为三种情况：

  

  

g[i]分为三种情况：

 

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

  

因为根据上面的状态转移方程我们可以看到所有情况里最少也是1，所以我们可以将f表和g表全部初始化为1，那样的话上面的6种情况就只用考虑两种情况

4. 填表顺序 

  

本题的填表顺序是：从左往右，两个表一起填

5. 返回值 ：题目要求 + 状态表示     

    

本题的返回值是：两个表里的最大值

4.  代码

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n=arr.size();
        vector<int>f(n,1),g(n,1);

        int ret=1;//因为最少也是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;
            ret=max(ret,max(f[i],g[i]));
        }
        return ret;
    }
};

未完待续~