978. 最长湍流子数组 - 力扣（LeetCode）

题目要求：

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：

• 若 i <= k < j ：
  • 当 k 为奇数时， A[k] > A[k+1]，且
  • 当 k 为偶数时，A[k] < A[k+1]；
• 或 若 i <= k < j ：
  • 当 k 为偶数时，A[k] > A[k+1] ，且
  • 当 k 为奇数时， A[k] < A[k+1]。

示例 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

示例 3：

输入：arr = [100]
输出：1

提示：

• 1 <= arr.length <= 4 * 104
• 0 <= arr[i] <= 109

解法-1 动态规划 O(N)：

        这个题与每日一练：等差数列划分-CSDN博客类似，nums[i] 能否与前面的数组构成湍流数组取决于nums[i]与nums[i]的大小关系，具体是大于还是小于又取决于nums[i-1]与nums[i-2]的大小关系，所以dp表需要初始化前两个位置。

        创建一个dp表f，存放以 i 为结尾的最长湍流数组的长度，填表的具体情况在代码中体现：

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();if (n <= 1)return n;vector<int> f(n);// 初始化f[0] = 1;if (arr[0] == arr[1])f[1] = 1;elsef[1] = 2;int ret = f[1];for (int i = 2; i < n; i++) {if (arr[i] > arr[i - 1] && arr[i - 1] < arr[i - 2] ||arr[i] < arr[i - 1] && arr[i - 1] > arr[i - 2]) {f[i] = f[i - 1] + 1; // arr[i]与前面构成湍流数组} else if (arr[i] == arr[i - 1]) { // 不构成湍流数组且与arr[i-1]也不构成湍流数组f[i] = 1;} else { // 不构成湍流数组，但是与arr[i-1]构成长度为2的湍流数组f[i] = 2;}ret = max(ret, f[i]);}return ret;}
};

        优化-滑动数组减少内存消耗：

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();if (n <= 1)return n;int a,b,c;a = 1;if(arr[0]==arr[1])b = 1;elseb = 2;int ret = b;for (int i = 2; i < n; i++) {if (arr[i] > arr[i - 1] && arr[i - 1] < arr[i - 2] ||arr[i] < arr[i - 1] && arr[i - 1] > arr[i - 2]) {c = b + 1; // arr[i]与前面构成湍流数组} else if (arr[i] == arr[i - 1]) { // 不构成湍流数组,且与arr[i-1]也不构成湍流数组c = 1;} else { // 不构成湍流数组，但是与arr[i-1]构成长度为2的湍流数组c = 2;}a = b;b = c;ret = max(ret, b);}return ret;}
};