418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I

ข้อ 1

[Dasgupta, Papadimitriou, Vazirani 6.1] ลำดับย่อยที่ติดกันของลำดับ $S\,$ คือสมาชิกกลุ่มหนึ่งของลำดับ $S\,$ ที่อยู่ติดกัน ยกตัวอย่างเช่นถ้า $S\,$ คือลำดับ

5, 15, -30, 10, -5, 40, 10

แล้ว 15, -30, 10 เป็นลำดับย่อยที่ติดกันของ $S\,$ แต่ 5, 15, 40 ไำม่ใช่ จงหาอัลกอริทึมเพื่อแก้ปัญหาทางการคำนวณต่อไปนี้

ข้อมูลเข้า: ลำดับของจำนวน $a_{1},a_{2},\ldots ,a_{n}\,$

ข้อมูลออก: ลำดับย่อยที่ติดกันทีมีผลบวกรวมของตัวเลขที่อยู่ในลำดับย่อยนั้นมากที่สุด (ลำดับที่มีความยาว 0 มีผลบวกรวมเท่ากับ 0)

สำหรับตัวอย่างข้างบน คำตอบคือ 10, -5, 40, 10 ซึ่งมีผลบวกรวมเท่ากับ 55