【算法】【动规】最长湍流子数组

跳转汇总链接

👉🔗算法题汇总链接

1.3 最长湍流子数组

🔗题目链接

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
ps: 就是元素两两之间的增长情况是 ↗↘↗↘↗… 这样

1. 状态表示：
   • 分析就 i 位置的走向来说（把这里的箭头起始位置当作 i-1 位置箭头指向位置当作 i 位置），有三种情况，向上↗，向下↘，平→。对 i-1 到 i 来说，依赖 i-2 的情况，所以这里需要建立两张 dp 表；
   • f[i] 表示以 i 位置为结尾的，并以↗为结尾的最长湍流子数组的长度；
   • g[i] 表示以 i 位置为结尾的，并以↘为结尾的最长湍流子数组的长度。
2. 状态转移方程：
   • 对 f 表和 g 表分三种情况进行讨论，这里将 i-1、i 位置的值表示为 a、b：

   f[i] = 
   	b>a, g[i-1] + 1
   	b<=a, 1
   g[i] = 
   	b>=a, 1
   	b<a, f[i-1] + 1		
   

3. 初始化
   • 表头置 1，或者 vector 的值都初始化为 1（b = a 的情况就可以不用考虑了）。
4. 填表顺序
   • 从左往右。
5. 返回值
   • 两张表中的最大值。

🐎代码如下：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        size_t n = arr.size();
        vector<size_t> f(n, 1); // 为上
        auto g = f;       		// 为下
        size_t maxRes = 1;
        for(size_t i = 1; i < n; i++)
        {
            if(arr[i] > arr[i-1])
            {
                f[i] = g[i-1] + 1;
            }
            else if(arr[i] < arr[i-1])
            {
                g[i] = f[i-1] + 1;
            }
            maxRes = max(max(g[i], f[i]), maxRes);
        }
        return maxRes;
    }
};

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(????) 若有差错恳请留言指正~~