Quà của Phú ông

Tên file bài làm: MAX1.*

Bờm vừa dành chiến thắng trong cuộc thi đặc biệt của Phú ông. Với tính keo kiệt của mình Phú ông chỉ cho Bờm chọn 1 số phần quà liên tục nhau được đặt sẵn trên bàn. Thật may với bảo bối của Đô-rê-mon Bờm nhanh chóng nhận ra giá trị các phần quà.

Giá trị n phần quà của Phú ông có thể xem là một dãy các số nguyên a₁, a₂,…,a_n trong đó a_i là giá trị của phần quà thứ i. Nếu a_i  âm thì phần quà đó không có ý nghĩa với Bờm mà ngược lại Bờm lại thấy thật khó chịu vì phải tốn |a_i | tiền thuê xe mang nó về nhà rồi cũng chẳng biết làm gì với nó.

Hãy giúp Bờm chọn được một dãy liên tục các phần quà sao cho tổng giá trị là lớn nhất.

Dữ liệu vào: từ tệp MAX1.INP

+ Dòng đầu tiên ghi số nguyên dương n (n≤10⁶)

+ Dòng thứ 2 chứa n số nguyên a_i tương ứng với giá trị của phần quà thứ i (|a_i|≤10⁹)

Dữ liệu ra: ghi vào tệp MAX1.OUT một số nguyên duy nhất là giá trị của bài toán

Ví dụ:

MAX1.INP	MAX1.OUT
4 1 3 -2 4	6

 Giải thích: Bờm có thể chọn tất cả các phần quà của Phú ông.

Test - Solution - code - đề (word)

next