ก่อนอื่นให้เราเปลี่ยนตัวเลขให้เป็นบวกหรือลบตามที่โจทย์กำหนดมาให้ เราจะเรียกลำดับนี้ว่า $A_i$

สังเกตว่าการใส่วงเล็บไว้ข้างหลังเครื่องหมาย + จะไม่ได้ทำให้ผลลัพธ์เปลี่ยนแปลงในกรณีใด ๆ ดังนั้นเราจึงสามารถสรุปได้ว่าหากเราจะใส่วงเล็บ เราจะใส่มันไว้หลังเครื่องหมาย - เท่านั้น

ต่อจากนี้ ให้เรายุบตัวเลขที่เป็นบวกและติดกันเข้าเป็นตัวเลขเดียว ซึ่งเป็นผลรวมของตัวเลขนั้น ๆ เช่น 3 -2 7 1 -3 5 -7 7 -9 8 6 กลายเป็น 3 -2 8 -3 5 -7 7 -9 14

ลำดับที่ได้มาจะเขียนได้ในรูป $p_0\ -q_1\ p_1\ -q_2\ ...\ p_{n-1}\ -q_n\ p_n$ โดย $p_i \geq 0$ และ $q_i > 0$

สมมติว่าวงเล็บเปิดแรกที่เราจะใส่จะอยู่ ณ ตำแหน่งของ $-q_k$ เราสามารถทำให้ผลรวมของส่วนของลำดับตั้งแต่ $-q_{k+1}\ p_{k+1}\ -q_{k+2}\ p_{k+2}\ -q_n\ p_n$ เป็นบวกทั้งหมด ด้วยวิธีการจัดวงเล็บดังนี้

$-(q_k+p_k - (q_{k+1} + p_{k+1}) - (q_{k+2} + p_{k+2}) - ... - (q_{n} + p_{n}))$

จะเห็นได้ว่าการใส่วงเล็บปิดที่ตำแหน่งสุดท้ายเป็นวิธีที่ดีที่สุดแล้ว เพราะ

• การปิดวงเล็บหลัง $q_k$ เลยนั้นจะไม่มีผลใด ๆ
• การปิดวงเล็บหลังตัวเลขใด ๆ ใน $p_k$ จะแย่กว่าการไม่ปิดวงเล็บใด ๆ เลย
• การปิดวงเล็บ ณ​ ตำแหน่งอื่น ๆ ใน $q_{k+1}, p_{k+1}, ..., q_{n-1}, p_{n-1}$ จะแย่กว่าการปิดวงเล็บในตำแหน่งสุดท้ายเสมอ เนื่องจากตัวเลขหลังจากนั้นในการปิดวงเล็บตำแหน่งสุดท้ายจะเป็นบวกเสมอ

ดังนั้นในการหาคำตอบของเรา เราจะไล่ตำแหน่งการใส่วงเล็บเปิดตำแหน่งแรก โดยในแต่ละตำแหน่งเราสามารถคำนวณคำตอบที่ดีที่สุดได้ตามที่เหล่ากล่าวไว้ข้างต้น จากนั้นให้เลือกค่าที่มีค่ามากที่สุด

การคำนวณคำตอบที่ดีที่สุดนั้นสามารถทำได้โดยการใช้ prefix sum

ดังนั้นเราสามารถแก้โจทย์ข้อนี้ได้ในเวลา $\mathcal{O}(N)$