Найдите длину самого длинного растущего последовательного подмассива
Опубликовано: 20 Сентября, 2022
Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы найти длину самого длинного возрастающего подмассива, чтобы элементы в подмассиве были последовательными целыми числами.
Примеры:
Input: arr[] = {1, 9, 3, 4, 20, 2}
Output: 2
Explanation: The subarray {3, 4} is the longest subarray of consecutive elementsInput: arr[] = {36, 41, 56, 32, 33, 34, 35, 43, 32, 42}
Output: 4
Explanation: The subarray {32, 33, 34, 35} is the longest subarray of consecutive elements
Подход: Идея состоит в том, чтобы запустить цикл и сохранить количество и максимум (оба изначально равны нулю). Выполните шаги, указанные ниже:
- Запустите цикл от начала до конца.
- Если текущий элемент не равен (предыдущему элементу+1), установите счетчик равным 1.
- В противном случае увеличьте количество.
- Обновите max с максимальным значением count и max.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(1)