418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 1
นิยามค่า
ให้ มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่อยที่ิคิดกันที่มีช่องสุดท้ายอยู่ที่ช่อง เราจะได้ว่า
![{\displaystyle a[i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77c9a5a9d0b2cc5583d6d4f5ddfed5cb677cfcee)
เราสามารถพิสูจน์ว่าสมการข้่างบนเป็นจริงได้ด้วย induction ดังต่อไปนี้
(Base Case) ในกรณีนี้ เราจะได้ว่ามีลำดับย่อยที่ติดกันที่จบที่ช่อง อยู่เพียงแค่ลำดับย่อยเดียว คือ ลำดับย่อยทีี่มีช่อง เีพียงช่องเดียว ฉะนั้น ตามต้องการ
![{\displaystyle OPT(1)=a[1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4630cfbdc49794c88ecef38676f052796dfa8dd5)
(Induction Case) สมมติว่า มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่ยอที่ติดกันที่มีช่องสุดท้ายอยู่ที่ช่อง สำหรับ บางค่า พิจารณาลำดับย่อยที่มีผลบวกมากที่สุดจบที่ช่อง เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน
- ลำดับย่อยนั้นเริ่มต้นที่ช่อง ด้วย ในกรณีนี้
- ลำดับย่อยนั้นไม่ได้เริ่มต้นที่ช่อง ในกรณีนี้เราจะได้ว่าลำดับย่อยนั้นเกิดจากการนำเอาลำดับย่อยที่จบที่ช่อง มาต่อกับช่อง ฉะนั้นผลรวมที่มากที่สุดของลำดับย่อยนี้คือ
![{\displaystyle a[i+1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fda867fc7040c638dd396a829f2a1abfc470eaa)
![{\displaystyle OPT(i+1)=a[i+1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65c1c12f20eb21d5fbb0a64b608dff406a015b6a)
เมื่อรวมสองกรณีข้างบนเข้าด้วยกัน เราจะได้ว่า
![{\displaystyle OPT(i+1)=\max(a[i+1],OPT(i)+a[i+1])\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fab7c12b355cd768e84bc8af760cf665c1e05480)
ดั้งนั้นเราจึงสรุปได้ว่าสมการข้างบนเป็นจริงสำหรับค่า ทุกค่า
การคำนวณค่า
เราสามารถคำนวณตาราง โดยที่ ได้ดังต่อไปนี้ <geshi lang="C">
![{\displaystyle M[i]=OPT(i)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6f063f25ebb510eed95078ece7ae366041b690f)
M[1] = a[1]
for i = 2 to n do
M[i] = max(a[i], M[i-1] + a[i])
</geshi> เห็นได้อย่างชัดเจนว่าอัลกอรืทึมส่วนนี้ทำงานได้ในเวลา
การหาช่วงที่มีผลบวกมากที่สุด
เราสามารถหาตำแหน่งของช่องสุดท้ายของช่วงที่มีผลบวกมากที่สุดได้ด้วยการหาค่า ที่ทำให้ มากที่สุด
ที่เหลือคือเราจะต้องหาช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น เราสามารถทำได้โดย pseudocode ต่อไปนี้ <geshi lang="C">
i = j
while (M[i] != a[i]) do
i = i - 1
</geshi> ค่า หลังจากที่ loop ทำงานเสร็จจะมีค่าเท่ากับช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น
ที่เป็นเช่นนี้เพราะว่า จากสมการข้างบน หากช่วงที่จบที่ นั้นเริ่มต้นจาก ด้วย มิเช่นนั้น ดังนั้นหากเราพบช่วงที่ แสดงว่าช่วงที่จบที่ นั้นเกิดจากการเอาช่วงที่จบที่ มาต่อกับช่อง ดังนั้นเราจึงสามารถหาตำแหน่งเริ่มต้นของช่วงที่จบที่ ด้วยการไปหาตำแหน่งเริ่มต้นของช่วงที่จบที่ แทน
![{\displaystyle OPT(i)=OPT(i-1)+a[i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8421e8e09db91a3808ee41979205be05289d9273)
![{\displaystyle a[i-1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e8b55512d464b0c5f3fcab40f0f8930d0ed74e2)
จาก pseudocode ข้างบน เราได้ว่าเราสามารถหาตำแหน่งสิ้นสุด ของช่วงได้ในเวลา และหาตำแหน่งเริ่มต้น ได้ในเวลา เช่นกัน ดังนั้นอัลกอริทึมทั้งหมดจึงทำงานได้ในเวลา
