dp最长湍流子数组

当 A 的子数组 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]。
也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。

返回 A 的最大湍流子数组的长度。

 

示例 1：

输入：[9,4,2,10,7,8,8,1,9]
输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])
示例 2：

输入：[4,8,12,16]
输出：2
示例 3：

输入：[100]
输出：1
 

提示：

1 <= A.length <= 40000
0 <= A[i] <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-turbulent-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我们可以定义两个子问题，分别对应最后一段上升和下降的波形子数组：

• 子问题 f(k) 为数组 A[0..k) 中，以 A[k-1] 结尾，且最后一段为“上升”的最长波形子数组；
• 子问题 g(k) 为数组 A[0..k) 中，以 A[k-1] 结尾，且最后一段为“下降”的最长波形子数组。

那么我们的子问题递推关系就变得清晰了起来：

• 如果 A[k-1] 和 A[k-2] 之间是“上升”，那么 $f(k) = g(k-1) + 1$，$g(k) = 1$；
• 如果 A[k-1] 和 A[k-2] 之间是“下降”，那么 $f(k) = 1$，$g(k) = f(k-1) + 1$；
• 如果 A[k-1] 和 A[k-2] 之间是“水平”，那么 $f(k) = 1$，$g(k) = 1$。

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        if (arr.length < 2) return 1;

        int n = arr.length;
        int[] asc = new int[n + 1];
        int[] desc = new int[n + 1];
        int max = 1;

        asc[1] = 1;
        desc[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (arr[i - 1] > arr[i - 2]) {
                asc[i] = desc[i - 1] + 1;               // 升序的等于如果前面是降序的，那么加上前面降序的已累计的结果数量，如果前面也是升序的，那么这个数由0变成了0+1
                desc[i] = 1;
            } else if (arr[i - 1] < arr[i - 2]) {
                desc[i] = asc[i - 1] + 1;               // 降序的等于如果前面是升序的，那么加上前面升序的已累计的结果数量，如果前面也是降序的，那么这个数由0变成了0+1
                asc[i] = 1;
            } else {                                    // 如果既不是升序也不是降序，那么都是1
                asc[i] = 1;
                desc[i] = 1;
            }
            max = Math.max(asc[i], max);                // 计算最大值
            max = Math.max(desc[i], max);
        }
        return max;
    }
}

public int maxTurbulenceSize(int[] A) {
    if (A.length <= 1) {
        return A.length;
    }
    
    int N = A.length;
    int[] f = new int[N+1];
    int[] g = new int[N+1];
    f[1] = 1;
    g[1] = 1;
    
    int res = 1;
    for (int k = 2; k <= N; k++) {
        if (A[k-1] > A[k-2]) {
            f[k] = g[k-1] + 1;
        } else {
            f[k] = 1;
        }
        if (A[k-1] < A[k-2]) {
            g[k] = f[k-1] + 1;
        } else {
            g[k] = 1;
        }
        res = Math.max(res, f[k]);
        res = Math.max(res, g[k]);
    }
    return res;
}

参考文献

作者：nettee
链接：https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/qing-xi-yi-dong-de-dong-tai-gui-hua-jie-fa-shi-yon/

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信