n개의 다른 숫자와 다른 양의 정수 K로 구성된 배열 A가 있다고 가정하고, 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 :=0으로 채워지는 크기(k + 1)의 배열
-
my_dict의 각 키에 대해 수행
-
키 <=k인 경우
-
나는 :=1
-
동안 키 * i <=k, 수행
-
count[키 * i] :=count[키 * i] + my_dict[키]
-
나는 :=나는 + 1
-
-
-
그렇지 않으면
-
루프에서 나오다
-
-
-
1cm :=0, 크기 :=0
-
범위 1에서 k + 1까지의 i에 대해 수행
-
개수[i]> 크기이면
-
크기 :=개수[i]
-
lcm :=나는
-
-
-
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