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)\,$ เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ

จากการที่เราใช้เทคนิค divide and conquer จะสามารถแสดงขั้นตอนต่าง ๆ ได้ดังนี้

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

• CONQUER: ทำการหาช่วงที่มีผลบวกมากที่สุดในอะเรย์ครึ่งซ้ายและครึ่งขวา

• COMBINE: ทำการหาช่วงที่มีผลบวกมากที่สุดข้ามฝั่งซ้ายขวา นั่นคือมีตำแหน่งเริ่มต้นของช่วง $i\,$ โดยที่ $1\leq i\leq k\,$ และตำแหน่งสิ้นสุดของช่วง $j\,$ โดยที่ $k+1\leq j\leq 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 ได้ดังนี้

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

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

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

</geshi>

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

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

   maxR <--- -infinity
   sum <--- 0
   for j=k+1 to n  // for loop นี้อีก n/2 
       sum <--- sum + a[j]
       if sum > maxR
           maxR = v
           maxiR=k
           maxjR=j

</geshi>

เมื่อได้ฟังก์ชั่นในการหาค่าผลบวกมากที่สุดในด้านซ้ายและขวาแล้ว ก็สามารถเขียนอัลกอริทึมที่ใช้ในการหาช่วงที่มีผลบวกมากที่สุด โดยวิธี divide and conquer ได้ดังนี้

<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])
       (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย
               (iR,jR,mR) <--- Maxinterval(ar,n-k)
       (maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
               (maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา
                maxi <--- maxiL // maxi เป็นตัวแปรที่เก็บตำแหน่งเริ่มต้นของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งเริ่มต้นของฝั่งซ้าย
                maxj <--- maxjR // maxj เป็นตัวแปรที่เก็บตำแหน่งเริ่มสุดท้ายของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งสุดท้ายของฝั่งขวา
                max <--- maxL + maxR // max เก็บค่าผลบวกที่มากที่สุดระหว่างสองฝั่ง จึงเท่ากับผลบวกที่มากที่สุดฝั่งซ้ายบวกกับผลบวกที่มากที่สุดฝั่งขวา
                if mL >= mR then // ถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดด้านขวา
                {
            if mL >= max then // และถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
                         {
                 i <--- iL  // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านซ้าย
                                   j <--- jL
                 m <--- mL
            }else{          // ผลบวกมากสุดด้านซ้ายมากกว่าด้านขวา แต่น้อยกว่าผลบวกข้ามซ้ายขวา
                                   i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
                                   j <--- maxj
                 m <--- max
            }
        }else  // ถ้าผลบวกมากสุดด้านขวามากกว่าผลบวกมากสุดด้านซ้าย
                {
            if mR >= max then // และถ้าผลบวกมากสุดด้านขวามากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
                         {
                 i <--- iR // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านขวา
                                   j <--- jR
                 m <--- mR
            }else{        // ผลบวกมากสุดด้านขวามากกว่าด้านซ้าย แต่น้อยกว่าผลบวกข้ามซ้ายขวา
                                   i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
                                   j <--- maxj
                 m <--- max
            }           
       }
       return (i,j,m) 

</geshi>