Найти наибольший непрерывный сегмент Арифметическая прогрессия

Question

• Учитывая диапазон целых чисел, скажем, A = [a1, a2, a3, a4, ... aN] и общая разница D
• Я должен найти длину наибольшего непрерывного сегмента чиселв приведенном выше массиве, которые образуют арифметическую прогрессию с общей разницей D.
• Приведенный пример A = [2,3,5,7,9,12,14,18] общая разница D = 2
• Наибольшее значение - [3,5,7,9], длина = 4.

Сначала я попробовал сделать это, используя проверку грубой силы для каждого возможного массива con-sub. Но это занимает много времени для больших массивов

def ap(test,d):
    l=len(test)
    if l==1:
        return True
    elif l>1:    
        for i in range(l-1):
            if test[i+1]-test[i]!=d:
                return False
                break
        else:
            return True
arr=list(map(int,input().split()))
d=int(input()) # common diff
length=0
for i in range(n):
    for j in range(i+1,n+1):
        if ap(arr[i:j],d):
            lon=len(arr[i:j])
            if lon>length:
                length=lon
print(length)

Answer 1

Эта проблема намного проще, чем "длинная-возрастающая-последовательная-подпоследовательность", потому что 1) у вас есть различие и 2) вам нужно непрерывное подмассив

Так что достаточно пройтисьчерез массив один раз, проверяя, нужна ли текущей паре соседей разница и длина прогрессии приращения, когда true

for i in range(1, len(A)):
    if A[i]-A[i-1] == d:
         curlen += 1
         maxlen = max(maxlen, curlen)
    else 
         curlen=1