Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

👨‍💻 Алгоритм:

1⃣Инициализируйте переменные для отслеживания текущего основания и максимальной длины горного массива.

2⃣Для каждого индекса, который может быть началом горного массива, определите пиковый элемент и найдите правую границу горного массива.

3⃣Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function longestMountain($arr) {
        $n = count($arr);
        $ans = 0;
        $base = 0;

        while ($base < $n) {
            $end = $base;
            if ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
                while ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
                    $end++;
                }
                if ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
                    while ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
                        $end++;
                    }
                    $ans = max($ans, $end - $base + 1);
                }
            }
            $base = max($end, $base + 1);
        }

        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний