Найдите длину самого длинного растущего последовательного подмассива

Опубликовано: 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 elements

Input: 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ