Длина самого длинного подмассива Фибоначчи

Для заданного массива arr[] целых элементов задача состоит в том, чтобы найти длину наибольшего подмассива из arr[] так, чтобы все элементы подмассива были числами Фибоначчи.

Примеры:

Input: arr[] = {11, 8, 21, 5, 3, 28, 4}
Output: 4
Explanation:
Maximum length sub-array with all elements as Fibonacci number is {8, 21, 5, 3}.

Input: arr[] = {25, 100, 36}
Output: 0

Подход: Эта проблема может быть решена путем обхода массива arr[] . Выполните следующие действия, чтобы решить эту проблему.

• Инициализируйте переменные, скажем, max_length и current_length равными 0 , чтобы сохранить максимальную длину подмассива и текущую длину подмассива, чтобы каждый элемент в подмассиве был числом Фибоначчи.
• Итерация в диапазоне [0, N-1] с использованием переменной i :
  • Если текущее число является числом Фибоначчи, увеличьте current_length на 1 , в противном случае установите current_length равным 0.
  • Теперь назначьте max_length как максимум из current_length и max_length.
• После выполнения вышеуказанных шагов выведите max_length в качестве требуемого ответа.

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

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