Tìm dãy con dài nhất của một mảng có LCM nhiều nhất là K trong Python

Giả sử chúng ta có một mảng A gồm n số khác nhau và một số nguyên dương K khác, chúng ta phải tìm dãy con dài nhất trong mảng có Nhiều nhất Chung (LCM) ít nhất là K. Sau khi trả về LCM và độ dài của dãy con. - dãy số, theo sau các chỉ số (bắt đầu từ 0) của các phần tử của dãy con thu được. Nếu không, trả về -1.

Vì vậy, nếu đầu vào là A =[3, 4, 5, 6], K =20, thì đầu ra sẽ là LCM =12, Length =3, Indexes =[0,1,3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A

• my_dict:=một bản đồ

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

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

• count:=một mảng có kích thước (k + 1) điền bằng 0

• đối với mỗi khóa trong my_dict, hãy thực hiện

  • phím if <=k, then

    • i:=1

    • trong khi phím * i <=k, thực hiện

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

      • i:=i + 1

  • nếu không,

    • đi ra từ vòng lặp

• lcm:=0, kích thước:=0

• đối với tôi trong phạm vi từ 1 đến k + 1, hãy thực hiện

  • nếu đếm [i]> kích thước thì

    • size:=count [i]

    • lcm:=i

• nếu lcm giống 0 thì

  • trả về -1

• nếu không,

  • hiển thị lcm và kích thước

  • đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

    • nếu lcm mod A [i] giống 0 thì

      • hiển thị tôi

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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)

Đầu vào

[3, 4, 5, 6] , 20

Đầu ra

LCM = 12, Length = 3 Index values: 0 1 3