Постановка проблемы:

Подмассив A[i], A[i+1], ..., A[j] массива A называется турбулентным тогда и только тогда, когда:

  • Для i <= k < j, A[k] > A[k+1], когда k нечетное, и A[k] < A[k+1], когда k четное;
  • ИЛИ, для i <= k < j, A[k] > A[k+1], если k четное, и A[k] < A[k+1], если k нечетное.

То есть подмассив является турбулентным, если знак сравнения меняется между каждой соседней парой элементов в подмассиве.

Возвращает длину турбулентного подмассива максимального размера A.

Пример 1:

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Пример 2:

Input: [4,8,12,16]
Output: 2

Пример 3:

Input: [100]
Output: 1

Примечание.

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

Решение:

package leetcode.contests.contest_120;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

public class LongestTurbulentSubarray {
    LongestTurbulentSubarray lon;

    @BeforeEach
    public void init() {
        lon = new LongestTurbulentSubarray();
    }

    @Test
    public void testFirst() {
        int res = lon.maxTurbulenceSize(new int[]{9, 4, 2, 10, 7, 8, 8, 1, 9});
        Assertions.assertEquals(5, res);
    }

    @Test
    public void testSecond() {
        int res = lon.maxTurbulenceSize(new int[]{4, 8, 12, 16});
        Assertions.assertEquals(2, res);
    }

    @Test
    public void testThird() {
        int res = lon.maxTurbulenceSize(new int[]{100});
        Assertions.assertEquals(1, res);
    }

    @Test
    public void testFour() {
        int res = lon.maxTurbulenceSize(new int[]{0, 1, 1, 0, 1, 0, 1, 1, 0, 0});
        Assertions.assertEquals(5, res);
    }


    public int maxTurbulenceSize(int[] A) {
        if (A == null || A.length == 0) return 0;
        if (A.length == 1) return 1;
        int len = A.length;
        int[][] tr = new int[A.length][2];
        tr[len - 1] = new int[]{0, 0};
        int max = 0;

        for (int i = len - 2; i >= 0; i--) {
            int target = targetGreater(tr, i + 1);
            System.out.println(target);
            if (target == 3) {
                if (A[i] > A[i + 1]) {
                    tr[i] = new int[]{0, 2};
                } else if (A[i] < A[i + 1]) {
                    tr[i] = new int[]{2, 0};
                } else {
                    tr[i] = new int[]{0, 0};
                }
            } else if (target == 1) {
                if (A[i] > A[i + 1]) {
                    tr[i] = new int[]{0, tr[i + 1][0] + 1};
                } else if (A[i] < A[i + 1]) {
                    tr[i] = new int[]{2, 0};
                } else {
                    tr[i] = new int[]{0, 0};
                }
            } else if (target == 2) {
                if (A[i] > A[i + 1]) {
                    tr[i] = new int[]{0, 2};
                } else if (A[i] < A[i + 1]) {
                    tr[i] = new int[]{tr[i + 1][1] + 1, 0};
                } else {
                    tr[i] = new int[]{0, 0};
                }
            }
            max = Math.max(max, Math.max(tr[i][0], tr[i][1]));
        }
        return max;
    }

    public int targetGreater(int[][] tr, int pos) {
        //1 greater
        //2 smaller
        //3 any
        if (tr[pos][0] > tr[pos][1])
            return 1;
        else if (tr[pos][0] < tr[pos][1])
            return 2;
        else return 3;
    }
}