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

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

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

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

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

<geshi lang="c"> 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

} </geshi>

<geshi lang="c"> 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

} </geshi>

<geshi lang="c"> 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
           } //end for k
         } //end for j
    } //end for i
     return count

} </geshi>

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