algorithm - 找到最大的连续段算术级数

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)

标签： algorithmmath

Answer 1

这个问题比“最长递增连续子序列”更简单，因为 1）你有差异，2）你需要连续的子数组

所以遍历数组一次就足够了，检查当前的邻居对是否需要差异并在为真时增加进展长度

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