418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 7

อินพุต:อะเรย์ขนาด $n\,$ ช่อง แต่ละช่องมีจำนวนเต็มบรรจุอยู่หนึ่งตัว

เอาพุต: คู่ลำดับ $(i,j)\,$ ที่ $1\leq i\leq j\leq n\,$ ที่ทำให้ $A[i]+A[i+1]+...+A[j]\,$ มีค่ามากที่สุด

แนวคิด วัตถุที่ต้องการตรวจสอบคือ คู่ลำดับ ดังนั้นคู่ลำดับที่เป็นไปได้ คือ $(1,1),(1,2),...,(1,n),(2,2),(2,3),...,(2,n),...,((n-1),n)\,$ ส่วนเงื่อนไขคือ คู่ลำดับ $(i,j)\,$ ดังกล่าวข้างต้นที่ $1\leq i\leq j\leq n\,$ ที่ทำให้ $A[i]+A[i+1]+...+A[j]\,$ มีค่ามากที่สุด

ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น $O(n\log n)\,$ นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ $T(n)=2T(n/2)+O(n)\,$ จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน $O(n)\,$ เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ

คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดระหว่างสองกลุ่ม การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากทีสุดระหว่างสองกลุ่มนั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ $A[k]\,$ กับ $A[k+1]\,$ อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ $A[1],A[2],...,A[k]\,$ ส่วนกลุ่มขวาเป็นอะเรย์ $A[k+1],A[k+2],...,A[n]\,$) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดระหว่างสองกลุ่มนี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า $A[k]\,$ ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ $A[k+1]\,$ ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง

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

<geshi lang="c"> Maxinterval(a,n)

   if n= 1
       return a
   else
       k=n/2
       al <--- (a[1],a[2],...,a[k]) // เป็นปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
       ar <--- (a[k+1],a[k+2],...,a[n])
       x <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย
               y <--- Maxinterval(ar,n-k)
       L <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
               R <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา
               maxi <--- maxiL // maxi เป็นตัวแปรที่เก็บตำแหน่งเริ่มต้นของช่วงที่มีผลบวกมากที่สุดระหว่างฝั่งซ้ายกับฝั่งขวา ดังนั้นจึงเท่ากับ ตำแหน่งเริ่มต้นของฝั่งซ้าย
               maxj <--- maxjR // maxj เป็นตัวแปรที่เก็บตำแหน่งเริ่มสุดท้ายของช่วงที่มีผลบวกมากที่สุดระหว่างฝั่งซ้ายกับฝั่งขวา ดังนั้นจึงเท่ากับ ตำแหน่งสุดท้ายของฝั่งขวา
               max <--- maxL + maxR // max เก็บค่าผลบวกที่มากที่สุดระหว่างสองฝั่ง จึงเท่ากับผลบวกที่มากที่สุดฝั่งซ้ายบวกกับผลบวกที่มากที่สุดฝั่งขวา

</geshi>

<geshi lang="c"> IntervalL(x,y,k)

   for i=k down to 1 // เวลาการทำงาน for loop นี้จะเป็น n/2
       v=value(a,i,k) // หาผลบวกของอะเรย์ตำแหน่งที่ i ถึง k
       if v > maxL // เก็บช่วงที่มีผลบวกมากสุดไว้
           maxL = v
           maxiL=i
           maxjL=k

</geshi>

<geshi lang="c"> IntervalR(x,y,k) for j=k+1 to n // for loop นี้อีก n/2

       v=value(a,k+1,j)
       if v > maxR
           maxR = v
           maxiR=k
           maxjR=j

</geshi>

<geshi lang="c"> value(a,i,j)

   for k = i to j
       result <--- result + a[k]
   return result

</geshi>