Xét dãy các số nguyên gồm n phần tử a1, a2, ..., an. Một dãy con liên tiếp của dãy
a1, a2, ..., an là dãy số nguyên có dạng ai, ai+1, ai+2, ..., aj (1≤ i ≤ j ≤ n).
Yêu cầu: Cho trước dãy các số nguyên a1, a2, ..., an. Hãy tìm một dãy con liên tiếp của dãy đã cho có tổng các phần tử đạt lớn nhất.
Ví dụ: Cho dãy 5, -3, 7, -9. Một dãy con liên tiếp của dãy này có tổng các phần tử đạt lớn nhất là dãy 5, -3, 7. Khi đó, tổng lớn nhất là S = 5 - 3 + 7 = 9.
Dữ liệu: Vào từ file văn bản DAYCON.INP gồm 2 dòng:
Kết quả: Ghi ra file văn bản DAYCON.OUT một số duy nhất là tổng các phần tử của dãy con liên tiếp đạt lớn nhất.
Có ít nhất 60% số test ứng với 60% số điểm của bài có 1 ≤ n ≤ 100.