/**
1. 状态定义: f[i] 表示以i结尾的交变数组的最大长度
2. 状态计算: 以最后一个位置 i 划分:
2.1 将其接到前面:  分为3 种情况 -> 连续3个符合交变数组 : f[i] = f[i-1] + 1
                                 A[i] != A[i-1] && A[i-2] == A[i-1]: f[i] = f[i-1] + 1  (相当于从A[i-1]开始的)
                                 连续3个严格单调: f[i] = 2  (相当于从A[i-1]开始的)
2.2 独立: 当 A[i] == A[i-1]时, 必须重新开始 f[i] = 1

3. 边界: f[~] = 0, f[0] = 1, f[1] = f[1] == f[0] ? 1 : 2; 为了方便手动计算前两个
4. 相乘可能爆 int , 需要用long
5. 仅依赖前一项, 所以可以滚动压缩, 节省空间
6. 注意判断的顺序不能乱
*/

class Solution {

    public int maxTurbulenceSize(int[] A) {
        // return dynamicProgramming(A);
        return zipDp(A);
    }

    public int dynamicProgramming(int[] A){
        if (A.length <= 1) return A.length;
        int n = A.length;
        int[] f = new int[n];
        f[0] = 1;
        f[1] = A[0] == A[1] ? 1 : 2;
        for (int i = 2 ; i < A.length ; i++){
            long prev = A[i-2] - A[i-1];
            long cur = A[i] - A[i-1];

            if (prev * cur > 0) {
                f[i] = f[i-1] + 1;
            } else if (cur == 0 ){
                f[i] = 1;
            } else if (prev == 0){
                f[i] = f[i-1] + 1;
            } else {
                f[i] = 2;
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }

    public int zipDp(int[] A) {
        if (A.length <= 1) return A.length;
        int maxV = A[0] == A[1] ? 1 : 2;
        int result = maxV;
        for (int i = 2 ; i < A.length ; i++){
            long prev = A[i-2] - A[i-1];
            long cur = A[i] - A[i-1];

            if (prev * cur > 0) {
                maxV ++ ;
            } else if (cur == 0 ){
                maxV = 1;
            } else if (prev == 0){
                maxV ++;
            } else {
                maxV = 2;
            }
            result = Math.max(result, maxV);
        }
        return result;
    }
}