cs_002 Đoạn con liên tiếp có tổng lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
cs002 Dãy con liên tiếp có tổng lớn nhất Cho dãy a gồm số nguyên. Nhiệm vụ của bạn là tìm mảng con trong a có tổng lớn nhất. Ví dụ mảng A= { -1 4 3 9 -20 5 9 -6 3 4 -100 5 8} thì đoạn con {4 3 9 } có tổng max = 16.
Dữ liệu vào gồm 2 dòng. Dòng thứ nhất chứa số nguyên n. Dòng thứ 2 chứa chứa n số nguyên tương ứng với a[0] đến a[n-1].
Dữ liệu ra gồm 3 số trên 1 dòng, cách nhau bởi dấu cách. Số thứ nhất là tổng max, số thứ 2 là vị trị bắt đầu đoạn con, số thứ 3 là vị trí kết thúc. Nếu dãy có nhiều đoạn con cùng tổng thì lấy đoạn sau cùng. Ví dụ: Input 13 -1 4 3 9 -20 5 9 -6 3 4 -100 5 8
Output 16 1 3
Ràng buộc dữ liệu
0<n<10^7</p>
-10^18 <a[i]<10^18</p>
Bình luận
a