Kỳ thi chọn học sinh giỏi cấp tỉnh môn Tin học Lớp 9 - Năm học 2017-2018

Bài 1. Đoạn con có tổng lớn nhất (6,0 điểm)

Cho một dãy gồm N số nguyên a1, a2,…, aN (N<250). Một đoạn con của dãy từ phần tử thứ p đến phần tử thứ q gồm liên tiếp các số ap, …, ap (1<=p<=q<=N). Hãy viết chương trình tìm một đoạn con có tổng lớn nhất của dãy N số đã cho.

Dữ liệu vào là file DOANCON.INP có cấu trúc như sau:

• Dòng thứ nhất chứ số nguyên N.
• Dòng tiếp theo chứa N số nguyên a1, a2, …, aN;  các số kề nhau cách nhau một khoảng trắng.

Dữ liệu ra là file DOANCON.OUT có cấu trúc như sau :

• Dòng thứ nhất chứa một số là tổng các phần tử của đoạn con tìm được.
• Dòng thứ 2 gồm hai số nguyên dương p, q chỉ vị trí bắt đầu và vị trí kết thúc của đoạn con trong dãy.