Самый длинный подмассив со всеми четными или всеми нечетными элементами

Опубликовано: 21 Сентября, 2022

Дан массив A[ ] из N неотрицательных целых чисел. Задача состоит в том, чтобы найти длину самого длинного подмассива, при котором все элементы в этом подмассиве четные или нечетные.

Примеры:

Input: A[] = {2, 5, 7, 2, 4, 6, 8, 3}
Output: 4
Explanation: Sub-array {2, 4, 6, 8} of length 4 has all even elements

Input: A[] = {2, 3, 2, 5, 7, 3} 
Output: 3
Explanation: Sub-array {5, 7, 3} of length 3 has all odd elements  

Наивный подход. Наивный подход к решению этой проблемы состоит в том, чтобы рассмотреть все смежные подмассивы и для каждого подмассива проверить, все ли элементы четные или нечетные. Самый длинный из них и будет ответом.
Временная сложность: O(N^2)
Вспомогательное пространство: O(1)

Эффективный подход: основная идея для решения этой проблемы состоит в том, чтобы использовать динамическое программирование (у него есть оба свойства — оптимальная подструктура и перекрывающиеся подзадачи), так что если есть несколько смежных нечетных элементов, то самый следующий нечетный элемент увеличит длину этого непрерывный массив по одному. И это верно и для четных элементов. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте массив dp[ ] , где dp[i] хранит длину подмассива, который заканчивается на A[i] .
  • Инициализируйте dp[0] с 1 .
  • Инициализируйте переменную ans как 1 , чтобы сохранить ответ.
  • Переберите диапазон [1, N], используя переменную i , и выполните следующие шаги:
    • Если A[i]%2 равно A[i-1]%2, тогда установите значение dp[i] как dp[i-1]+1.
    • В противном случае установите значение dp[i] равным 1.
  • Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
    • Установите значение ans как максимальное значение ans или dp[i].
  • После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

Оптимизация пространства: можно дополнительно оптимизировать пространственную сложность описанного выше подхода, заметив, что для вычисления dp[i] имеет значение только значение dp[i-1] . Итак, сохраните dp[i-1] в переменной и обновляйте переменную на каждой итерации. Кроме того, обновляйте ответ на каждой итерации. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменные dp как 1 , чтобы сохранить длину подмассива до i-1 , и как 1 , чтобы сохранить ответ.
  • Переберите диапазон [1, N], используя переменную i , и выполните следующие шаги:
    • Если A[i]%2 равно A[i-1]%2, тогда установите значение dp как dp+1 и установите значение ans как максимальное значение ans или dp.
    • В противном случае установите значение dp равным 1.
  • После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)

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