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

2023-12-15 15:03:44

跳转汇总链接

👉🔗算法题汇总链接


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

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


文章来源:https://blog.csdn.net/m0_67470729/article/details/134994855
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。