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)+a[i+1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d0f1489fe5aafad9c61ae955cbe92826b454bcb)
เมื่อรวมสองกรณีข้างบนเข้าด้วยกัน เราจะได้ว่า
ดั้งนั้นเราจึงสรุปได้ว่าสมการข้างบนเป็นจริงสำหรับค่า ทุกค่า
การคำนวณค่า
เราสามารถคำนวณตาราง โดยที่ ได้ดังต่อไปนี้ <geshi lang="C">
![{\displaystyle M[\cdot ]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfb3571832e86e1b8899e759bb8a1ec800718e4d)
M[1] = a[1]
for i = 2 to n do
M[i] = max(a[i], M[i-1] + a[i])
</geshi> เห็นได้อย่างชัดเจนว่าอัลกอรืทึมส่วนนี้ทำงานได้ในเวลา
การหาช่วงที่มีผลบวกมากที่สุด
เราสามารถหาตำแหน่งของช่องสุดท้ายของช่วงที่มีผลบวกมากที่สุดได้ด้วยการหาค่า ที่ทำให้ มากที่สุด
![{\displaystyle M[j]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/419475a82fa5ece74130df1e04d3f9460a135d0f)
ที่เหลือคือเราจะต้องหาช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น เราสามารถทำได้โดย pseudocode ต่อไปนี้ <geshi lang="C">
i = j
while (M[i] != a[i]) do
i = i - 1
</geshi> ค่า หลังจากที่ loop ทำงานเสร็จจะมีค่าเท่ากับช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น
ที่เป็นเช่นนี้เพราะว่า จากสมการข้างบน หากช่วงที่จบที่ นั้นเริ่มต้นจาก ด้วย มิเช่นนั้น ดังนั้นหากเราพบช่วงที่ แสดงว่าช่วงที่จบที่ นั้นเกิดจากการเอาช่วงที่จบที่ มาต่อกับช่อง ดังนั้นเราจึงสามารถหาตำแหน่งเริ่มต้นของช่วงที่จบที่ ด้วยการไปหาตำแหน่งเริ่มต้นของช่วงที่จบที่ แทน
![{\displaystyle OPT(i)=a[i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d69a807ca60ecb3a165553397917d1bde4b5437)
จาก pseudocode ข้างบน เราได้ว่าเราสามารถหาตำแหน่งสิ้นสุด ของช่วงได้ในเวลา และหาตำแหน่งเริ่มต้น ได้ในเวลา เช่นกัน ดังนั้นอัลกอริทึมทั้งหมดจึงทำงานได้ในเวลา
