大小>=2的所有子阵列中的最大GCD

Question

给定一个数组，编写一个程序，在所有大小为>；=给定数组的2 示例：2 3 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）

意味着不需要计算大于2的GCD，如果增加子阵列的大小，则GCD保持不变或减小。 如果您增加大小，则Gcd不会增加

计算大小为2的子阵的GCD为O（2*N），几乎等于O（N）

我想你明白我想说的