โจทย์: กำหนดอาร์เรย์ A, B หา bitonic sequence ยาวที่สุด: ส่วนเพิ่ม (strictly increasing) เป็น subsequence ของ A, ส่วนลด (strictly decreasing) เป็น subsequence ของ B
ตัวอย่าง: A=[2,6,3,5,4,6], B=[9,7,5,8,4,3] → [2,3,4,6,9,7,5,4,3]
อัลกอริทึม: LIS (Longest Increasing Subsequence) แบบ Patience Sorting
- หา LIS ของ A → ได้ส่วนเพิ่ม (เก็บลำดับย้อนกลับด้วย prev_idx)
- กลับลำดับ B → หา LIS ของ B ที่กลับแล้ว = LDS (Longest Decreasing Subsequence) ของ B เดิม
- รวมทั้งสองส่วน
ตัวอย่างโค้ด
answer = []
def index_ceiling(arr, T, left, right, key):
while right - left > 1:
mid = left + (right - left) // 2
if arr[T[mid]] >= key:
right = mid
else:
left = mid
return right
def long_inc_seq(A):
n = len(A)
tails_idx = [0] * n
prev_idx = [-1] * n
length = 1
for i in range(1, n):
if A[i] < A[tails_idx[0]]:
tails_idx[0] = i
elif A[i] > A[tails_idx[length-1]]:
prev_idx[i] = tails_idx[length-1]
tails_idx[length] = i
length += 1
else:
pos = index_ceiling(A, tails_idx, -1, length-1, A[i])
prev_idx[i] = tails_idx[pos-1]
tails_idx[pos] = i
i = tails_idx[length-1]
while i >= 0:
answer.append(A[i])
i = prev_idx[i]
def long_bitonic(A, B):
global answer
answer = []
long_inc_seq(A)
answer = answer[::-1] # LIS of A (increasing)
B = B[::-1]
long_inc_seq(B) # LIS of reversed B = LDS of B
return answer
A = [2, 6, 3, 5, 4, 6]
B = [9, 7, 5, 8, 4, 3]
long_bitonic(A, B)
print(answer) # [2, 3, 4, 6, 9, 7, 5, 4, 3]
ผลลัพธ์
[2, 3, 4, 6, 9, 7, 5, 4, 3]
สรุป: ใช้ LIS O(n log n) แบบ Patience Sorting หาทั้งส่วนเพิ่มและส่วนลด (ผ่านการกลับอาร์เรย์) รวมกันได้ bitonic sequence
