动态规划算法之子数组系列----最长湍流子数组

最长湍流子数组 

最长湍流子数字

问题描述

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。如果比较符号在子数组中的每个相邻元

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：

输入：arr = [4,8,12,16]
输出：2

湍流子数组的简单解释：

算法原理

1. 状态表示

以 i 位置结尾的数组，结合 i - 1 位置可以分为上升或下降趋势，判断是否为湍流数组还要结合 i - 1以前的位置进行判断，故需要两个dp表进行状态表示。

f [ i ] :表示以 i 位置结尾的所有子数组中，最后呈现上升状态的最长湍流子数组长度。

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

2. 状态转移方程

(1)对于f[i]可以分以下情况讨论

• nums[i-1]  >= nums[i]   则nums[i]自己构成一个湍流子数组,f[i] = 1;
• nums[i-1] < nums[i], 则i-1以前需要呈现一个下降趋势，故有 f[i] = g [i-1] +1;

(2)对于g[i]可以分为以下情况讨论

• nums[i-1]  >nums[i]    则i-1以前需要呈现一个上升趋势，故有 g[i] = f [i-1] +1;;
• nums[i-1] <= nums[i], 则nums[i]自己构成一个湍流子数组,g[i] = 1;

3. 初始化

在最差的情况下，每个元素也可以构成一个湍流子数组，即f 表和g表最差情况下都是1，故可以将f和g表中的全部元素初始化为1 

4.填表顺序

从左向右，两张表一起填

5.返回值

结合题意和fg表的状态表示，可以知道本题返回的是 f 和 g 表中的最大值

代码编写

int maxTurbulenceSize(vector<int>& arr) 
    {
        int n = arr.size();
        vector<int> f(n,1);
        auto g = f;
        int ret = 1;  //最差情况就是1 所以将ret初始值设置为1
        for(int i = 1; i < n; i++)
        {
            //i-1 到 i 位置呈下降趋势，则i-2到i-1 位置需要呈现上升趋势
            if(arr[i-1] > arr[i]) g[i] = f[i-1] + 1;
            
            //i-1 到 i 位置呈上升趋势，则i-2到i-1 位置需要呈现下降趋势
            if(arr[i-1] < arr[i]) f[i] = g[i-1] + 1;

            //返回f表和g表中的最大值
            ret = max(ret,max(f[i],g[i]));
        }
        return ret;
    }

复杂度分析

本题使用一次for循环、创建了两个大小为n 的数组，所以时间复杂度是O(n),空间复杂度是O(n)。