我的划分序列代码有什么问题？

Question

我试图对这个问题进行编码：

这个问题是关于正整数序列a1，a2，.，aN。序列的子序列是通过删除某些元素获得的。例如，3,7,11,3是6,3,11,5,7,4,3,11,5,3，3，3,3,7是6,3,11,5,7,4,3,11,5,3的子序列。 给定一个整数序列，你的目标是找到这个序列的最长全除法子序列的长度。 全分割序列是一个序列a1，a2，…，aN，其中ai在i< j时对aj进行分割，例如，3，15，60,720是一个全分割序列。

我的代码是：

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中。

Answer 2

这解决了您的问题，而不使用任何递归:)

n = int(input())
ar = []
bestvals = []
best_stored = []
for x in range(n):
  ar.append(int(input()))
  best_stored.append(0)

best_stored[0] = 1

for i in range(n):
  maxval = 1
  for j in range(i):
    if ar[i] % ar[j] == 0:
      maxval = max(maxval,(best_stored[j])+1)
  best_stored[i] = maxval

print(max(best_stored))

Answer 3

对于我在评论中提到的图论解决方案：

class Node(object):
    def __init__(self, x):
        self.x = x
        self.children = []

    def add_child(self, child_x):
        # Not actually used here, but a useful alternate constructor!
        new = self.__class__(child_x)
        self.children.append(new)
        return new

    def how_deep(self):
        """Does a DFS to return how deep the deepest branch goes."""

        maxdepth = 1
        for child in self.children:
            maxdepth = max(maxdepth, child.how_deep()+1)
        return maxdepth

nums = [9, 2, 3, 7, 8, 14, 39, 145, 76, 320]
nodes = [Node(num) for num in nums]
for i,node in enumerate(nodes):
    for other in nodes[i:]:
        if other.x % node.x == 0:
            node.children.append(other)
# graph built, rooted at nodes[0]

result = max([n.how_deep() for n in nodes])