Сложность: 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 {
public:
int longestMountain(vector<int>& A) {
int N = A.size();
int ans = 0, base = 0;
while (base < N) {
int end = base;
if (end + 1 < N && A[end] < A[end + 1]) {
while (end + 1 < N && A[end] < A[end + 1]) end++;
if (end + 1 < N && A[end] > A[end + 1]) {
while (end + 1 < N && A[end] > A[end + 1]) end++;
ans = max(ans, end - base + 1);
}
}
base = max(end, base + 1);
}
return ans;
}
};Ставь 👍 и забирай 📚 Базу знаний