dp最长湍流子数组

2020-10-03

978. 最长湍流子数组

难度中等140收藏分享切换为英文接收动态反馈

当 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：

1
2
3

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

示例 2：

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

示例 3：

1 2	输入：[100] 输出：1

提示：

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

动态规划

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

子问题 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;
    }
}

滑动窗口

avatar

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int ret = 1;
        int left = 0, right = 0;

        while (right < n - 1) {
            if (left == right) {
                if (arr[left] == arr[left + 1]) {
                    left++;
                }
                right++;
            } else {
                if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
                    right++;
                } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
                    right++;
                } else {
                    left = right;
                }
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/zui-chang-tuan-liu-zi-shu-zu-by-leetcode-t4d8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


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;
                desc[i] = 1;
            } else if (arr[i - 1] < arr[i - 2]) {
                desc[i] = asc[i - 1] + 1;
                asc[i] = 1;
            } else {
                asc[i] = 1;
                desc[i] = 1;
            }
            max = Math.max(asc[i], max);
            max = Math.max(desc[i], max);
        }
        return max;
    }
}

参考文献

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

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