python - 我的分割序列代码有什么问题

Question

我正在尝试对这个问题进行编码:

This problem is about sequences of positive integers a1,a2,...,aN. Asubsequence of a sequence is anything obtained by dropping some of theelements. For example, 3,7,11,3 is a subsequence of6,3,11,5,7,4,3,11,5,3 , but 3,3,7 is not a subsequence of6,3,11,5,7,4,3,11,5,3 .

Given a sequence of integers your aim is to find the length of the longest fully dividing subsequence of this sequence.

A fully dividing sequence is a sequence a1,a2,...,aN where ai dividesaj whenever i < j. For example, 3, 15, 60, 720 is a fully dividingsequence.

我的代码是:

n=input()
ar=[]

temp=0
for i in range (0,n):
    temp=input()
    ar.append(temp)

def best(i):
    if i==0:
        return (1)
    else:
        ans =1
        for j in range (0,i):
            if (ar[j]%ar[i]==0):

                ans=max(ans,(best(j)+1))
         return (ans)
an=[]
for i in range (0,n):
   temp=best(i)
   an.append(temp)

print max(an)

输入是

9
2 
3 
7 
8 
14 
39 
145 
76 
320

我应该得到 3(因为 2、8、320)作为输出，但我得到 1

Answer 1

作为j < i ，你需要检查是否a[j]是 a[i] 的分隔符，反之亦然。所以这意味着你需要设置这个条件(并且只有这个条件，而不是与逆条件相结合):

        if (ar[i]%ar[j]==0):

通过此更改，给定示例数据的输出为 3。

混淆来自定义，其中 i < j ，而在您的代码中 j < i .