418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 7

อินพุต:อะเรย์ขนาด $n\,$ ช่อง แต่ละช่องมจำนวนเต็มบรรจุอยู่หนึ่งตัว

เอาพุต: คู่ลำดับ $(i,j)\,$ ที่ $1\leq i\leq j\leq n\,$ ที่ทำให้ $A[i]+A[i+1]+...+A[j]\,$ มีค่ามากที่สุด

แนวคิด วัตถุที่ต้องการตรวจสอบคือ คู่ลำดับ ดังนั้นคู่ลำดับที่เป็นไปได้ คือ $(1,1),(1,2),...,(1,n),(2,2),(2,3),...,(2,n),...,((n-1),n)\,$ ส่วนเงื่อนไขคือ คู่ลำดับ $(i,j)\,$ ดังกล่าวข้างต้นที่ $1\leq i\leq j\leq n\,$ ที่ทำให้ $A[i]+A[i+1]+...+A[j]\,$ มีค่ามากที่สุด

ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น $O(n\log n)\,$ นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ $T(n)=2T(n/2)+O(n)\,$ จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นสองปัญหาย่อย ๆ ให้มีขนาดเท่า ๆ กัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน $O(n)\,$ เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ