在 Python 中找到 LCM 至多 K 的数组的最长子序列

假设我们有一个由 n 个不同数字组成的数组 A 和另一个正整数 K，我们必须找到数组中最长的子序列，其中最小公倍数(LCM)最多为 K。然后返回 LCM 和子序列的长度-sequence，跟随所获得子序列的元素的索引（从0开始）。否则，返回-1。

所以，如果输入像 A = [3, 4, 5, 6], K = 20，那么输出将是 LCM = 12, Length = 3, Indexes = [0,1,3]

在线示例

让我们看看以下实现以获得更好的理解 -

from collections import defaultdict
def get_seq(A,k):
   n = len(A)
   my_dict = defaultdict(lambda:0)
   for i in range(0, n):
      my_dict[A[i]] += 1
   count = [0] * (k + 1)
   for key in my_dict:
      if key <= k:
         i = 1
         while key * i <= k:
            count[key * i] += my_dict[key]
            i += 1
      else:
         break
   lcm = 0
   size = 0
   for i in range(1, k + 1):
      if count[i] > size:
         size = count[i]
         lcm = i
   if lcm == 0:
      print(-1)
   else:
      print("LCM = {0}, Length = {1}".format(lcm, size))
      print("指标值： ", end = "")
      for i in range(0, n):
         if lcm % A[i] == 0:
            print(i, end = " ")

k = 20
A = [3, 4, 5, 6]
get_seq(A,k)

输入

[3, 4, 5, 6] , 20

LCM = 12, Length = 3 指标值： 0 1 3