สมมติว่าเรามีอาร์เรย์ A ขนาด n ตัวเลขต่างกัน และจำนวนเต็มบวก K ต้องการหาลำดับย่อย (subsequence) ที่ยาวที่สุดซึ่ง LCM (ค่าต่ำสุดร่วม) ของสมาชิกไม่เกิน K คืนค่า LCM, ความยาว, และดัชนีของสมาชิก
เช่น A = [3, 4, 5, 6], K = 20 ผลลัพธ์ LCM = 12, Length = 3, Indexes = [0, 1, 3]
ขั้นตอนการแก้ปัญหา
- นับความถี่ของแต่ละตัวเลขใน A
- สร้างอาร์เรย์
countขนาด K+1 สำหรับนับจำนวนสมาชิกที่หารแต่ละค่า 1..K ลงตัว - สำหรับแต่ละคีย์ในแผนที่ ถ้าคีย์ ≤ K ให้เพิ่มความถี่เข้าไปใน
count[key*i]สำหรับทุก i ที่ key*i ≤ K - หาค่า i (1..K) ที่มี
count[i]มากที่สุด → นั้นคือ LCM และความยาว - คืนค่าดัชนีของสมาชิกที่หาร LCM ลงตัว
ตัวอย่างโค้ด Python
from collections import defaultdict
def get_seq(A, k):
n = len(A)
my_dict = defaultdict(lambda: 0)
for i in range(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(f"LCM = {lcm}, Length = {size}")
print("Index values:", end=" ")
for i in range(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
