418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 1

นิยามค่า $OPT\,$

ให้ $OPT(i)\,$ มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่อยที่ิคิดกันที่มีช่องสุดท้ายอยู่ที่ช่อง $a[i]\,$ เราจะได้ว่า

$OPT(i)={\begin{cases}a[1]&i=1\\\max(a[i],OPT(i-1)+a[i])&i>1\end{cases}}\,$

เราสามารถพิสูจน์ว่าสมการข้่างบนเป็นจริงได้ด้วย induction ดังต่อไปนี้

(Base Case) ในกรณีนี้ $i=1\,$ เราจะได้ว่ามีลำดับย่อยที่ติดกันที่จบที่ช่อง $a[1]\,$ อยู่เพียงแค่ลำดับย่อยเดียว คือ ลำดับย่อยทีี่มีช่อง $a[1]\,$ เีพียงช่องเดียว ฉะนั้น $OPT(1)=a[1]\,$ ตามต้องการ

(Induction Case) สมมติว่า $OPT(i)\,$ มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่ยอที่ติดกันที่มีช่องสุดท้ายอยู่ที่ช่อง $a[i]\,$ สำหรับ $i\geq 1\,$ บางค่า พิจารณาลำดับย่อยที่มีผลบวกมากที่สุดจบที่ช่อง $a[i+1]\,$ เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน

1. ลำดับย่อยนั้นเริ่มต้นที่ช่อง $a[i+1]\,$ ด้วย ในกรณีนี้ $OPT(i+1)=a[i+1]\,$
2. ลำดับย่อยนั้นไม่ได้เริ่มต้นที่ช่อง $a[i+1]\,$ ในกรณีนี้เราจะได้ว่าลำดับย่อยนั้นเกิดจากการนำเอาลำดับย่อยที่จบที่ช่อง $a[i]\,$ มาต่อกับช่อง $a[i+1]\,$ ฉะนั้นผลรวมที่มากที่สุดของลำดับย่อยนี้คือ $OPT(i)+a[i+1]\,$

เมื่อรวมสองกรณีข้างบนเข้าด้วยกัน เราจะได้ว่า $OPT(i+1)=\max(a[i+1],OPT(i)+a[i+1])\,$

ดั้งนั้นเราจึงสรุปได้ว่าสมการข้างบนเป็นจริงสำหรับค่า $i\,$ ทุกค่า

การคำนวณค่า $OPT\,$

เราสามารถคำนวณตาราง $M[\cdot ]\,$ โดยที่ $M[i]=OPT(i)\,$ ได้ดังต่อไปนี้ <geshi lang="C">

   M[1] = a[1]
   for i = 2 to n do
       M[i] = max(a[i], M[i-1] + a[i])

</geshi> เห็นได้อย่างชัดเจนว่าอัลกอรืทึมส่วนนี้ทำงานได้ในเวลา $O(n)\,$

การหาช่วงที่มีผลบวกมากที่สุด

เราสามารถหาตำแหน่งของช่องสุดท้ายของช่วงที่มีผลบวกมากที่สุดได้ด้วยการหาค่า $j\,$ ที่ทำให้ $M[j]\,$ มากที่สุด

ที่เหลือคือเราจะต้องหาช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น เราสามารถทำได้โดย pseudocode ต่อไปนี้ <geshi lang="C">

   i = j
   while (M[i] != a[i]) do
       i = i - 1

</geshi> ค่า $i\,$ หลังจากที่ loop ทำงานเสร็จจะมีค่าเท่ากับช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น

ที่เป็นเช่นนี้เพราะว่า จากสมการข้างบน $OPT(i)=a[i]\,$ หากช่วงที่จบที่ $a[i]\,$ นั้นเริ่มต้นจาก $a[i]\,$ ด้วย มิเช่นนั้น $OPT(i)=OPT(i-1)+a[i]\,$ ดังนั้นหากเราพบช่วงที่ $OPT(i)\neq a[i]\,$ แสดงว่าช่วงที่จบที่ $a[i]\,$ นั้นเกิดจากการเอาช่วงที่จบที่ $a[i-1]\,$ มาต่อกับช่อง $a[i]\,$ ดังนั้นเราจึงสามารถหาตำแหน่งเริ่มต้นของช่วงที่จบที่ $a[i]\,$ ด้วยการไปหาตำแหน่งเริ่มต้นของช่วงที่จบที่ $a[i-1]\,$ แทน

จาก pseudocode ข้างบน เราได้ว่าเราสามารถหาตำแหน่งสิ้นสุด $j\,$ ของช่วงได้ในเวลา $O(n)\,$ และหาตำแหน่งเริ่มต้น $i\,$ ได้ในเวลา $O(n)\,$ เช่นกัน ดังนั้นอัลกอริทึมทั้งหมดจึงทำงานได้ในเวลา $O(n)\,$