java - 在数组中找到最长的几何级数

我正在尝试实现一个动态编程算法来查找列表中最长几何级数的长度我遇到了这个算法：http://www.cs.illinois.edu/~jeffe/pubs/pdf/arith.pdf并试图修改它的几何级数但是，我不能让它工作。
我的代码是：

def dp(numbers):
  numbers = sorted(numbers)

  n = len(numbers)
  table = [[2] * n] * n
  for i in range(n):
    table[i][n - 1] = 2

  largest = 2
  for j in range(n - 1, -1, -1):
    i = j - 1
    k = j + 1
    while i >= 0 and k <= n - 1:
      if numbers[j] > math.sqrt(numbers[i] * numbers[k]):
        k += 1
      elif numbers[j] < math.sqrt(numbers[i] * numbers[k]):
        table[i][j] = 2
        i -= 1
      elif numbers[j] == math.sqrt(numbers[i] * numbers[k]):
        table[i][j] = table[j][k] +  1
        largest = max(largest, table[i][j])
        i -= 1
        k += 1

    while i >= 0:
      table[i][j] = 2
      i -= 1

  return largest

例如，如果我运行print dp([1, 2, 4, 8, 16, 32, 64])当它应该是7时得到4任何关于我做错的事情的帮助都是非常有帮助的。

最佳答案

问题在于：

table = [[2] * n] * n

这样做的目的是生成一个包含n个元素的列表n次问题是，由于这些列表是相同的（is-same，而不仅仅是==-same）列表而不是副本，所以它们都会一起更新，这是不好的，例如。，

>>> lst=[[2]]*2
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
True
>>> lst[0][0]=1
>>> lst
[[1], [1]]

解决办法是写

table = [[2] * n for i in range(n)]

它重复运行[2] * n以获得n个副本，这些副本最初是==-相同但不is-相同的。

>>> lst=[[2]for i in range(2)]
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
False
>>> lst[0][0]=1
>>> lst
[[1], [2]]

编辑：同样，for j in range(n - 1, -1, -1):应该是for j in range(n - 2, -1, -1):以精确匹配伪代码，尽管这不是错误的原因。

关于java - 在数组中找到最长的几何级数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23524766/