Максимальный GCD среди всех подмассивов размера> = 2

Question

Учитывая массив, напишите программу, чтобы найти максимальный gcd ​​среди всех подмассивов размера> = 2 данного массива. Пример: 2 3 4 4 4 Выход: 4 ([4, 4, 4])

Мой код:

from fractions import gcd
from functools import reduce
def GCD(arr):
   x = reduce(gcd, arr)
   return x
t = int(input())
for T in range(0, t):
   n = int(input())
   arr = list(map(int, input().split()))
   gcdd = -1
   for i in range(n):
      for j in range(i+2, n):
         gcdd = max(gcdd, GCD(arr[i:j]))
print(gcdd)

Это O (N ^ 2), это может быть еще более оптимизировано?

Answer 1

Я думаю, max (GCD (размер подмассива> = 2)) == max (GCD (размер подмассива == 2))

, потому что

предположим, что существует массив a, b , c, d

, затем GCD (a, b, c) = GCD (GCD (a, b), c)

среднее значение GCD (a, b, c) <= GCD (a, b) </p>

означает, что нет необходимости вычислять GCD размером более 2, если вы увеличиваете размер подмассива, GCD остается постоянным или уменьшается. Нет случая, если вы увеличите размер, тогда Gcd увеличится.

Вычислите GCD подмассива размера 2: O (2 * N), который почти равен O (N).

I думаю, вы понимаете, что я хочу сказать.