Page 52 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 52
2-42 โครงสร้างข้อมูลและขั้นตอนวิธี
Procedure MaxSubSequenceSum (A1, A2, …, An)
1 BEGIN /* คืนค่าผ ลลัพธ์จ ากการเรียกใช้ฟังก์ชันย่อย โดยร ะบุตำ�แหน่งเริ่มแ ละสิ้นส ุดล ำ�ดับ */
2 RETURN MaxSubSum (A1, A2, …, An, 1, n)
3 END
Procedure MaxSubSum(A1, A2, …, An, Left, Right) /*ฟังก์ชนั ยอ่ ย เพอ่ื ระบุตำ�แหน่งเริ่มและสิน้ ส ดุ ล�ำ ดับ */
1 BEGIN /* กรณีฐ าน ถ้าต ำ�แหน่งเริ่มกับส ิ้นส ุดลำ�ดับเท่าก ัน */
2 IF Left = Right THEN
3 BEGIN
4 IEFLASELRefEt T>U0RTNHAELNef t /* ถ้าจ ำ�นวนเต็มในต ำ�แหน่งนั้นม ากกว่าศูนย์ */
5 /* ให้ค ืนจ ำ�นวนเต็มในต ำ�แหน่งน ั้น */
6
7 RETURN 0 /* ถ้าน้อยกว่าหรือเท่ากับศ ูนย์ ให้คืนศูนย์ */
8 END
9 Center := ⎣(Left + Right)/2⎦ /* หาตำ�แหน่งก ึ่งกลางลำ�ดับ */
10 Max/*LeเรftียSกuใmช้ฟ:ัง=กM์ชันaยx่อSยuซbํ้าSเพumื่อห(Aาค1,่าผAล2ร, ว…ม,มAากn,ท Lี่สeุดfขt,อCงลeำ�nดteับrย) ่อยทางซ้าย แบบเวียนเกิด */
11 Max/*RเiรgียhกtSใชu้ฟmังก:=์ชันMยa่อxยSซuํ้าbเพSืu่อmห า(คA่า1ผ, ลAร2ว,ม…ม ,ากAทn,ี่สCุดขenองteล rำ�+ด1ับ,ยR่อigยhท tา)งข วา แบบเวียนเกิด */
12 MaxLeftBorderSum := 0 /* ให้ค่าเริ่มต้นผลร วมม ากท ี่สุดในครึ่งซ้ายที่ม ีจำ�นวนเต็มตัวส ุดท้าย */
13 LeftBorderSum := 0 /* ให้ค ่าเริ่มต ้นผ ลรวมในค รึ่งซ ้ายที่มีจำ�นวนเต็มตัวสุดท้าย */
14 FOR i := Center DOWN to Left DO
15 BEGIN /* ลูป for เพื่อห าผ ลรวมมากทสี่ ดุ ในค รงึ่ ซ า้ ยท่ีมจี ำ�นวนเต็มตวั ส ุดท้าย */
16 LeftBorderSum := >LeMftBaxoLrdeeftrBSourmde+rSAuim
17 IF LeftBorderSum THEN
18 MaxLeftBorderSum := LeftBorderSum
19 END
20 MaxRightBorderSum := /* ให้ค่าเริ่มต ้นผ ลร วมม ากที่สุดในครึ่งข วาท ี่ม ีจ ำ�นวนเต็มต ัวแรก */
21 RightBorderSum := 0 /* ให้ค ่าเริ่มต ้นผ ลรวมในค รึ่งข วาท ี่ม ีจำ�นวนเต็มต ัวแ รก */
22 FOR i := Center + 1 to Right DO
23 BEGIN /* ลูป for เพื่อห าผลร วมมากท ี่สุดในค รึ่งข วาที่มีจ ำ�นวนเต็มต ัวแ รก */
24 RightBorderSum := >RigMhatxBRoirgdhetrBSourmde+rSAuim
25 IF RightBorderSum THEN
26 MaxRightBorderSum := RightBorderSum
27 END
28 RETURN Max(MaxLeftSum, MaxRightSum, (MaxLeftBorderSum + MaxRightBorderSum))
/* คืนค่าม ากที่สุดของผลรวมล ำ�ดับย่อยท ั้งส ามต ำ�แหน่ง */
29 END
