78. 最长湍流子数组https://leetcode.cn/problems/longest-turbulent-subarray/description/

给定一个整数数组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 * 10^4，0 <= arr[i] <= 10^9。

---

我们用动态规划的思想来解决这个问题。

确定状态表示：根据经验和题目要求，我们用dp[i]表示：以i位置为结尾的所有子数组中，最长湍流子数组的长度。但是这样的状态表示推不出状态转移方程，所以我们需要更细的划分：

• 用f[i]表示：以i位置为结尾的所有最后呈现上升趋势的子数组中，最长湍流子数组的长度。
• 用g[i]表示：以i位置为结尾的所有最后呈现下降趋势的子数组中，最长湍流子数组的长度。

推导状态转移方程：考虑最近的一步。以i位置为结尾的湍流子数组和以i - 1位置为结尾的湍流子数组有什么关系呢？以f[i]为例，分类讨论：

• 如果arr[i - 1] >= arr[i]，那么以i位置为结尾的最后呈现上升趋势的最长湍流子数组就是arr[i]本身，即f[i] = 1。
• 如果arr[i - 1] < arr[i]，那么以i位置为结尾的最后呈现上升趋势的最长湍流子数组，就应该是「以i - 1位置为结尾的最后呈现下降趋势的最长湍流子数组」的末尾添加arr[i]之后，形成的湍流子数组，即f[i] = g[i - 1] + 1。

综上所述：f[i] = arr[i - 1] >= arr[i] ? 1 : g[i - 1] + 1。同理，g[i] = arr[i - 1] <= arr[i] ? 1 : f[i - 1] + 1。换句话说，f[i]和g[i]默认是1，如果arr[i - 1] < arr[i]，那么f[i] = g[i - 1] + 1；如果arr[i - 1] > arr[i]，那么g[i] = f[i - 1] + 1。

初始化：根据状态转移方程，我们需要初始化f[0]和g[0]的值，防止越界。显然f[0] = g[0] = 1。

填表顺序：根据状态转移方程，显然应从左往右，同时填两个表。

返回值：根据状态表示，由于我们不确定最长湍流子数组的结束位置，所以应返回f表和g表中，所有元素的最大值。

细节问题：显然f表和g表的规模和arr相同，均为1 x n。

时间复杂度：O(N)，空间复杂度：O(N)。

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

        // 创建dp表
        vector<int> f(n, 1);
        auto g = f;

        // 填表
        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;
            }
        }

        // 返回结果
        return max(*max_element(f.begin(), f.end()),
                   *max_element(g.begin(), g.end()));
    }
};