Page 50 - โครงสร้างข้อมูลและขั้นตอนวิธี

2-40 โครงสร้างข้อมูลและขั้นตอนวิธี

Procedure MaxSubSequenceSum (A1, A2, …, An)

1 BEGIN
2 MaxSum := 0 /* ให้​ค่าเ​ริ่มต​ ้น​ของผ​ ล​รวม​มากท​ ี่สุด MaxSum เป็น 0 */
3 FOR i := 1 to n DO /* ลูป for แรก เพื่อ​เป็น​ดัชนีเ​ริ่ม​ต้นข​ อง​ลำ�ดับ​ย่อย */
4 BEGIN /* ลูป for ซ้อน เพื่อ​เป็น​ดัชนีส​ ุดท้ายข​ อง​ลำ�ดับย​ ่อย */
5 FOR j := i to n DO /* ให้​ค่าเ​ริ่ม​ต้นข​ อง​ผลร​ วมล​ ำ�ดับย​ ่อย ThisSum เป็น 0 */
6 BEGIN /* ลูป for ซ้อน เพื่อเ​ป็นด​ ัชนีไ​ปย​ ังส​ มาชิก​ของล​ ำ�ดับ​ย่อย */
7 ThisSum := 0 /* หาผ​ ล​รวม​ของล​ ำ�ดับ​ย่อย */
8 FOR k := i to j DO /* ตรวจส​ อบผ​ ล​รวม​ย่อยเ​พื่อห​ าผ​ ล​รวมท​ ี่ม​ าก​ที่สุด */
9 BEGIN
10 ThisSum := ThisSum + Ak /* คืน​ค่า​ผล​รวม​ที่ม​ าก​ที่สุด */
11 END
12 IF ThisSum > MaxSum THEN
13 MaxSum := ThisSum
14 END
15 END
16 RETURN MaxSum
17 END

ขั้นต​ อน​วธิ ​ีที่ 2 จากข​ ้ัน​ตอนว​ ิธี​ที่ 1 จะเ​ห็นว​ ่า มีก​ ารใ​ช้​เวลาแ​ บบก​ �ำลังส​ าม (cubic) ซ่ึงท​ �ำให้​เมื่อ​ข้อมูล​มี​ขนาด​
ใกAหkΣาk=jญรiไ​เว่จ​พA้​แะ่ิมk​ทท​=คโ�นำดง่าAาเยพนjj​จทไ​่ือะ+ด​กี​​ลส ้​ช าัะง้ารเ​หkΣjก​ค—ข=1นต�้ัiนำน่ึ​ง​เต​ห=​ทวอ็นณ ี่​ล น​วAูปว​่าkิธkΣjใf—=ีท​ดoน1iี่ังr​ข2​นAทั้นจั้นkี่​ตึง2ส​ใอพ​านจนมิจ​ระ​วาาอ​ตริธรบณถี​้ทอ​ถล​ี่งา1ัดหล​ด​ไมดก​าป​ผีลข​า​ขรั้นูปลอ​ค​ต​รงf�ำoวอ​ลน​rมนูปวท​กณfี่าokΣ2j ร—= r1​ททiทkΣ�่ี​ม=ำjA่ีง2iีลาkนAูปเปใ​ทkหf็น่ี​ซoโม​ผํ้าrดซ่​ทลทย้อ​รุก​ล่ี น3ว​บคม​ลซ​กร​งข้อั้งาเ​อร​นพงซว​อ่ือ​ลึ่นงย​ก�​เล​ำู่ปดาเูปรพ็ับน​ลท​่ื​ยอกด่ี ​ห่อ3าลยราอูป​ค​ท​ทอ่าf�ี่​กกำoง�rำาแkΣลอน=jลังiอ​​พซ้วกA้ําเ​ิจกซ​ไาkป็บ้รอแ​หค​ณนตน่าา ่ลน่ึง​น ะล​่ันั่น​รูปkΣj—​เคอ=อ1iบือง​
ดัง​น้ัน ข้ัน​ตอน​วิธีท​ ี่ 2 จึง​ใช้​เวลา​ใน​การป​ ระมวล​ผล​น้อยล​ ง​เป็น O(n2) และเ​ขียนเ​ป็นขั้นตอนวิธี​ได้ ดังนี้

Procedure MaxSubSequenceSum (A1, A2, …, An)

1 BEGIN
2 MaxSum := 0 /* ให้ค​ ่าเ​ริ่มต​ ้น​ของผ​ ล​รวมม​ ากท​ ี่สุด MaxSum เป็น 0 */
3 FOR i := 1 to n DO /* ลูป for แรก เพื่อ​เป็น​ดัชนี​เริ่มต​ ้น​ของล​ ำ�ดับ​ย่อย */
4 BEGIN /* ให้​ค่าเ​ริ่ม​ต้นข​ องผ​ ลร​ วมล​ ำ�ดับ​ย่อย ThisSum เป็น 0 */
5 ThisSum := 0 /* ลูป for ซ้อน เพื่อ​เป็นด​ ัชนีส​ ุดท้ายข​ องล​ ำ�ดับย​ ่อย */
6 FOR j := i to n DO /* หา​ผล​รวม​ของล​ ำ�ดับย​ ่อย */
7 BEGIN /* ตรวจส​ อบผ​ ล​รวม​ย่อย​เพื่อห​ า​ผล​รวม​ที่​มากท​ ี่สุด */
8 ThisSum := ThisSum + TAHj EN
9 IF ThisSum > MaxSum /* คืน​ค่าผ​ ล​รวม​ที่ม​ าก​ที่สุด */
10 MaxSum := ThisSum
11 END
12 END
13 RETURN MaxSum
14 END