ปัญหาที่ตั้งขึ้นมาในข้อนี้เป็นหนึ่งใน classical problem หรือว่าได้ว่าเป็นปัญหาที่เจอได้บ่อยครั้ง คือปัญหา maximum sum subsequence ปัญหา maximum sum subsequence มีหลายวิธีที่สามารถจะแก้ได้โดยใช้เวลาเพียง $O(n)$ เท่านั้น เช่นเราอาจใช้ Kadane's algorithm หรือ deque มาแก้ก็ได้

อย่างไรก็ตาม เทคนิคเหล่านี้ยากเกินกว่าที่จะเหมาะสมกับโจทย์ในระดับ 10 เลยขออธิบายอัลกอริทึมที่ใช้เวลา $O(n^2)$ เนื่องจากโจทย์กำหนดว่า $n \leq 2500$ ดังนั้น $n^2 = 6250000$ ซึ่งยังสามารถทำงานเสร็จได้ภายในหนึ่งวินาทีสำหรับภาษา C/C++ แน่นอน

อัลกอริทึมที่ใช้ก็คำ for-loop สองชั้น โดยไล่ตัวแปร $i$ จาก $[0, n)$ และสำหรับแต่ละ $i$ จะไล่ตัวแปร $j$ ตั้งแต่ $[i, n)$ เราจะเก็บตัวแปร $S$ ที่เก็บผลบวกของช่วง $[i, j]$ เมื่อต้องการเลื่อนจาก $j$ ไป $j+1$ เราจะเพิ่มค่า $S$ เป็น $S = S + a[j]$ และเมื่อต้องการเปลี่ยนค่า $i$ เราจะตั้งค่า $S$ ใหม่ที่ $S = 0$ ฉนั้นในแต่ละขั้นตอนจะได้ช่วง $[i, j]$ และผลบวกของแต่ละช่วง ซึ่งสามารถนำมาหาว่าผลบวกของช่วงใหนมีค่ามากที่สุดได้ ด้านล่างคือโค้ดของอัลกอริทึมหลักนี้

max_sum = 0
left_bound = -1
right_bound = -1
for i in range(0, n):
    S = 0
    for j in range(i, n):
        S = S + a[j]
        if S > max_sum:
            max_sum = S
            left_bound = i
            right_bound = j
print(max_sum, left_bound, right_bound)