在 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