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

อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n)\,$

ข้อ 2

[Dasgupta, Papadimitriou, Vazirani 6.2] คุณกำลังจะเดินทางไกลบนถนนยาวเส้ันหนึ่ง คุณเริ่มต้นเดิน ณ หลักกิโลเมตรที่ 0 ริมถนนมีโรงแรมอยู่ $n\,$ โรงแรม ตั้งอยู่ที่ตำแหน่ง $a_{1},a_{2},\ldots ,a_{n}\,$ โดยที่ค่า $a_{i}\,$ แต่ละค่านั้นจะเริ่มวัดจากแหล่งกิโลเมตรที่ 0 คุณสามารถหยุดพักการเดินทางได้โรงแรม $n\,$ โรงแรมนี้เท่านั้น แต่คุณสามารถเลือกได้ว่าจะหยุดพักที่โรงแรมไหน และคุณจะสิ้นสุดการเดินทางที่โรงแรมสุดท้าย ซึ่งตั้งอยู่ที่ตำแหน่ง $a_{n}\,$

คุณต้องการที่จะเดินทางเป็นระยะทาง 200 กิโลเมตรต่อวัน แต่มันอาจจะเป็นไปไม่ได้ เนื่องจากโรงแรมอาจจะไม่อยู่ห่างกันเท่ากับ 200 กิโลเมตรพอดี ถ้าคุณเดินทางเป็นระยะทางเท่ากับ $x\,$ กิโลเมตรในวันหนึ่ง คุณจะได้รับ penalty เท่ากับ $(200-x)^{2}\,$ คุณต้องการที่จะวางแผนการเดินทางของคุณให้ได้รับ penalty รวมน้อยที่สุดเท่าที่จะทำได้

จงออกแบบอัลกอริทึมที่มีประสิทธิภาพสำหรับแก้ปัญหา