Pythonで最大KのLCMを持つ配列の最長のサブシーケンスを見つけます

n個の異なる数の配列Aと別の正の整数Kがあるとすると、最小公倍数（LCM）が最大でKの配列で最長のサブシーケンスを見つける必要があります。その後、LCMとサブの長さを返します。 -シーケンス、取得したサブシーケンスの要素のインデックス（0から開始）に従います。それ以外の場合は、-1を返します。

したがって、入力がA =[3、4、5、6]、K =20の場合、出力はLCM =12、長さ=3、インデックス=[0,1,3]

これを解決するには、次の手順に従います-

• n：=Aのサイズ

• my_dict：=マップ

• 0からnの範囲のiの場合、実行

  • my_dict [A [i]]：=my_dict [A [i]] + 1

• count：=サイズ（k + 1）の配列を0で埋める

• my_dictのキーごとに、実行します

  • キー<=kの場合、

    • i：=1

    • キー*i<=k、do

      • count [key * i]：=count [key * i] + my_dict [key]

      • i：=i + 1

  • それ以外の場合

    • ループから出てきます

• lcm：=0、サイズ：=0

• 1からk+1の範囲のiの場合、実行

  • count [i]> sizeの場合、

    • サイズ：=count [i]

    • lcm：=i

• lcmが0と同じ場合、

  • -1を返す

• それ以外の場合

  • lcmとサイズを表示

  • 0からnの範囲のiの場合、実行

    • lcm mod A [i]が0と同じ場合、

      • ディスプレイi

例

理解を深めるために、次の実装を見てみましょう-

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("Index values: ", 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 Index values: 0 1 3