418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 7

อินพุต: ลำดับของจำนวนเต็ม $n\,$ จำนวน และช่วง$[p,q]\,$

เอาพุต: จำนวนของลำดับย่อยที่มีพิสัยในช่วง$[p,q]\,$

แนวคิด ข้อนี้วัตถุที่เราสนใจคือ ช่วง เรามีวิธีในการหาช่วงแล้วในห้องเรียน เราจะใช้วิธีนั้นกัน ค่าของวัตถุที่เราสนใจก็คือ การนำค่ามากที่สุดในช่วง มาลบกับค่าที่น้อยที่สุดในช่วง ซึ่งวิธีในการหาค่ามากที่สุด กับน้อยที่สุดเราก็เรียนไปแล้วในห้องเรียน และเงื่อนไขในข้อนี้คือ พิสัยอยู่ในช่วง $[p,q]\,$ ดังนั้นเมื่อได้พิสัยของแต่ละช่วงมาแล้ว เราก็ต้องนำมาตรวจสอบว่าอยู่ในช่วงดังกล่าวหรือไม่ ถ้าอยู่ที่เพิ่มตัวนับจำนวนขึ้นไปเรื่อย ๆ

จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้

FINDMAX(A,i,j)

max<-- -1000000

for k=i to i<=j

if A[k] > max

max= A[k]

max_k=k

return max_k

FINDMIN(A,i,j)

min<-- 1000000

for k=i to k<=j

if A[k] < min

min= A[k]

min_k=k

return min_k

COUNTINTERVAL(A,n)

count <-- 0

for i=0 to i<n

for j=i to j<n

max=FINDMAX(A,i,j)

min=FINDMIN(A,i,j)

r=max-min

for k=p to k<=q

if r=k

count <-- count + 1

return count

เวลาการทำงานของอัลกอริทึม การหยิบลำดับย่อยแต่ละลำดับมาดู เราใช้ for loop สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก $O(n)\,$ ดังนั้นเวลารวมของสองขั้นตอนนี้คือ$O(n^{3})\,$ ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง $[p,q]\,$ หรือไม่ใช้เวลาอีก $q-p+1\,$ ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น $O(n^{3})\,$