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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 5 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 4: แถว 4:
  
 
แนวคิด วัตถุที่ต้องการตรวจสอบคือ คู่ลำดับ ดังนั้นคู่ลำดับที่เป็นไปได้ คือ <math> (1,1),(1,2),...,(1,n),(2,2),(2,3),...,(2,n),...,((n-1),n) \,</math> ส่วนเงื่อนไขคือ คู่ลำดับ <math> (i,j) \,</math> ดังกล่าวข้างต้นที่ <math> 1 \leq i \leq j \leq n \, </math> ที่ทำให้ <math>A[i]+A[i+1]+...+A[j] \,</math> มีค่ามากที่สุด
 
แนวคิด วัตถุที่ต้องการตรวจสอบคือ คู่ลำดับ ดังนั้นคู่ลำดับที่เป็นไปได้ คือ <math> (1,1),(1,2),...,(1,n),(2,2),(2,3),...,(2,n),...,((n-1),n) \,</math> ส่วนเงื่อนไขคือ คู่ลำดับ <math> (i,j) \,</math> ดังกล่าวข้างต้นที่ <math> 1 \leq i \leq j \leq n \, </math> ที่ทำให้ <math>A[i]+A[i+1]+...+A[j] \,</math> มีค่ามากที่สุด
 +
  
 
ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น <math> O(n \log n) \,</math> นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ <math>T(n)=2T(n/2)+O(n) \,</math> จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน <math> O(n) \, </math> เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ
 
ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น <math> O(n \log n) \,</math> นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ <math>T(n)=2T(n/2)+O(n) \,</math> จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน <math> O(n) \, </math> เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ
  
−
คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดระหว่างสองกลุ่ม การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากทีสุดระหว่างสองกลุ่มนั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ <math> A[k] \, </math> กับ  <math> A[k+1] \, </math> อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดระหว่างสองกลุ่มนี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า <math> A[k] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ <math> A[k+1] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง
+
จากการที่เราใช้เทคนิค divide and conquer จะสามารถแสดงขั้นตอนต่าง ๆ ได้ดังนี้
 +
 
 +
 
 +
*'''DIVIDE:''' แบ่งอะเรย์ออกเป็นสองครึ่งที่มีขนาดเท่ากัน สมมติให้  k เป็นตำแหน่งที่แบ่ง จะได้กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>)
 +
 
 +
*'''CONQUER:''' ทำการหาช่วงที่มีผลบวกมากที่สุดในอะเรย์ครึ่งซ้ายและครึ่งขวา
 +
 
 +
*'''COMBINE:''' ทำการหาช่วงที่มีผลบวกมากที่สุดข้ามฝั่งซ้ายขวา นั่นคือมีตำแหน่งเริ่มต้นของช่วง <math> i \, </math> โดยที่ <math> 1 \leq i \leq k \,</math> และตำแหน่งสิ้นสุดของช่วง <math> j \, </math> โดยที่ <math> k+1 \leq j \leq n \,</math>
 +
 
 +
 
 +
คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ <math> A[k] \, </math> กับ  <math> A[k+1] \, </math> อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า <math> A[k] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ <math> A[k+1] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง
  
 
จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
 
จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
 +
 +
ฟังก์ชั่น IntervalL มีไว้เพื่อหาค่าผลบวกที่มากที่สุดในอะเรย์ด้านซ้าย จากแนวคิดข้างต้น ที่บอกไว้ว่า ผลบวกที่มากที่สุดข้ามซ้ายขวา จะต้องมีอะเรย์ตำแหน่งที่ k อยู่ด้วยเสมอ จากนั้นเราต้องหาต่อไปว่า <math> A[k] \, </math> นี้ต้องบวกไปกับสมาชิกในอะเรย์ด้านซ้ายอีกกี่ตัวจึงจะมีค่าผลบวกมากที่สุด นั่นคือหาว่าค่าเริ่มต้นของช่วง <math> i \, </math> จะอยู่ตำแหน่งไหน ระหว่าง 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 อยู่ด้วยเสมอ จากนั้นเราต้องหาต่อไปว่า <math> A[k+1] \, </math> นี้ต้องบวกไปกับสมาชิกในอะเรย์ด้านขวาอีกกี่ตัวจึงจะมีค่าผลบวกมากที่สุด นั่นคือหาว่าค่าสิ้นสุดของช่วง <math> j \, </math> จะอยู่ตำแหน่งไหน ระหว่าง 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">
 
<geshi lang="c">
แถว 17: แถว 59:
 
     else
 
     else
 
         k=n/2
 
         k=n/2
−
         al <--- (a[1],a[2],...,a[k]) // เป็นปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
+
         al <--- (a[1],a[2],...,a[k]) // แบ่งปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
 
         ar <--- (a[k+1],a[k+2],...,a[n])
 
         ar <--- (a[k+1],a[k+2],...,a[n])
−
         (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกด้านซ้าย
+
         (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย
 
                 (iR,jR,mR) <--- Maxinterval(ar,n-k)
 
                 (iR,jR,mR) <--- Maxinterval(ar,n-k)
 
         (maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
 
         (maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
 
                 (maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา
 
                 (maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา
−
                maxi <--- maxiL // maxi เป็นตัวแปรที่เก็บตำแหน่งเริ่มต้นของช่วงที่มีผลบวกมากที่สุดระหว่างฝั่งซ้ายกับฝั่งขวา ดังนั้นจึงเท่ากับ ตำแหน่งเริ่มต้นของฝั่งซ้าย
+
                maxi <--- maxiL // maxi เป็นตัวแปรที่เก็บตำแหน่งเริ่มต้นของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งเริ่มต้นของฝั่งซ้าย
−
                maxj <--- maxjR // maxj เป็นตัวแปรที่เก็บตำแหน่งเริ่มสุดท้ายของช่วงที่มีผลบวกมากที่สุดระหว่างฝั่งซ้ายกับฝั่งขวา ดังนั้นจึงเท่ากับ ตำแหน่งสุดท้ายของฝั่งขวา
+
                maxj <--- maxjR // maxj เป็นตัวแปรที่เก็บตำแหน่งเริ่มสุดท้ายของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งสุดท้ายของฝั่งขวา
−
                max <--- maxL + maxR // max เก็บค่าผลบวกที่มากที่สุดระหว่างสองฝั่ง จึงเท่ากับผลบวกที่มากที่สุดฝั่งซ้ายบวกกับผลบวกที่มากที่สุดฝั่งขวา
+
                max <--- maxL + maxR // max เก็บค่าผลบวกที่มากที่สุดระหว่างสองฝั่ง จึงเท่ากับผลบวกที่มากที่สุดฝั่งซ้ายบวกกับผลบวกที่มากที่สุดฝั่งขวา
−
                if mL >= mR then // ถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดด้านขวา
+
                if mL >= mR then // ถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดด้านขวา
−
        {
+
                {
 
             if mL >= max then // และถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
 
             if mL >= max then // และถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
−
            {
+
                          {
 
                   i <--- iL  // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านซ้าย
 
                   i <--- iL  // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านซ้าย
−
                  j <--- jL
+
                                    j <--- jL
 
                   m <--- mL
 
                   m <--- mL
 
             }else{          // ผลบวกมากสุดด้านซ้ายมากกว่าด้านขวา แต่น้อยกว่าผลบวกข้ามซ้ายขวา
 
             }else{          // ผลบวกมากสุดด้านซ้ายมากกว่าด้านขวา แต่น้อยกว่าผลบวกข้ามซ้ายขวา
−
                  i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
+
                                    i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
−
                  j <--- maxj
+
                                    j <--- maxj
 
                   m <--- max
 
                   m <--- max
 
             }
 
             }
−
        }else  // ถ้าผลบวกมากสุดด้านขวามากกว่าผลบวกมากสุดด้านซ้าย
+
        }else  // ถ้าผลบวกมากสุดด้านขวามากกว่าผลบวกมากสุดด้านซ้าย
−
        {
+
                {
 
             if mR >= max then // และถ้าผลบวกมากสุดด้านขวามากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
 
             if mR >= max then // และถ้าผลบวกมากสุดด้านขวามากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
−
            {
+
                          {
 
                   i <--- iR // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านขวา
 
                   i <--- iR // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านขวา
−
                  j <--- jR
+
                                    j <--- jR
 
                   m <--- mR
 
                   m <--- mR
 
             }else{        // ผลบวกมากสุดด้านขวามากกว่าด้านซ้าย แต่น้อยกว่าผลบวกข้ามซ้ายขวา
 
             }else{        // ผลบวกมากสุดด้านขวามากกว่าด้านซ้าย แต่น้อยกว่าผลบวกข้ามซ้ายขวา
−
                  i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
+
                                    i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
−
                  j <--- maxj
+
                                    j <--- maxj
 
                   m <--- max
 
                   m <--- max
 
             }           
 
             }           
 
         }
 
         }
−
         return (i,j,m)
+
         return (i,j,m)  
−
</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>
 
</geshi>

รุ่นแก้ไขปัจจุบันเมื่อ 07:23, 8 กันยายน 2552

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

เอาพุต: คู่ลำดับ ที่ ที่ทำให้ มีค่ามากที่สุด

แนวคิด วัตถุที่ต้องการตรวจสอบคือ คู่ลำดับ ดังนั้นคู่ลำดับที่เป็นไปได้ คือ ส่วนเงื่อนไขคือ คู่ลำดับ ดังกล่าวข้างต้นที่ ที่ทำให้ มีค่ามากที่สุด


ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ

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


  • DIVIDE: แบ่งอะเรย์ออกเป็นสองครึ่งที่มีขนาดเท่ากัน สมมติให้ k เป็นตำแหน่งที่แบ่ง จะได้กลุ่มซ้ายเป็นอะเรย์ ส่วนกลุ่มขวาเป็นอะเรย์ )
  • CONQUER: ทำการหาช่วงที่มีผลบวกมากที่สุดในอะเรย์ครึ่งซ้ายและครึ่งขวา
  • COMBINE: ทำการหาช่วงที่มีผลบวกมากที่สุดข้ามฝั่งซ้ายขวา นั่นคือมีตำแหน่งเริ่มต้นของช่วง โดยที่ และตำแหน่งสิ้นสุดของช่วง โดยที่


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

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

ฟังก์ชั่น IntervalL มีไว้เพื่อหาค่าผลบวกที่มากที่สุดในอะเรย์ด้านซ้าย จากแนวคิดข้างต้น ที่บอกไว้ว่า ผลบวกที่มากที่สุดข้ามซ้ายขวา จะต้องมีอะเรย์ตำแหน่งที่ k อยู่ด้วยเสมอ จากนั้นเราต้องหาต่อไปว่า นี้ต้องบวกไปกับสมาชิกในอะเรย์ด้านซ้ายอีกกี่ตัวจึงจะมีค่าผลบวกมากที่สุด นั่นคือหาว่าค่าเริ่มต้นของช่วง จะอยู่ตำแหน่งไหน ระหว่าง 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 อยู่ด้วยเสมอ จากนั้นเราต้องหาต่อไปว่า นี้ต้องบวกไปกับสมาชิกในอะเรย์ด้านขวาอีกกี่ตัวจึงจะมีค่าผลบวกมากที่สุด นั่นคือหาว่าค่าสิ้นสุดของช่วง จะอยู่ตำแหน่งไหน ระหว่าง 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>

ดึงข้อมูลจาก "https://theory.cpe.ku.ac.th/wiki/index.php?title=418531_ภาคต้น_2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ_7&oldid=7329"