Đất Trạm 5G Tổng Cực Đại

Mô tả

Kỹ sư Viettel được giao nhiệm vụ khảo sát một dải đất dọc theo tuyến đường tỉnh để lắp đặt trạm phát sóng 5G. Tuyến đường được chia thành $n$ lô đất liên tiếp, mỗi lô rộng như nhau và đã được đo tín hiệu phủ sóng (đơn vị đo theo công nghệ AI đang thử nghiệm, có thể mang giá trị âm). Tín hiệu dương thể hiện vùng có thể phủ sóng rất tốt, âm là vùng có vật cản hoặc nhiễu sóng nặng.

Do ngân sách hạn hẹp, ban giám đốc chỉ cho phép đặt trạm trên một dải lô liên tiếp duy nhất (có thể là một lô hoặc nhiều lô liền nhau). Nhiệm vụ của bạn là chọn dải lô sao cho tổng tín hiệu trên dải đó là lớn nhất có thể. Nếu mọi lựa chọn đều cho tổng âm, bạn vẫn phải chọn một dải có ít nhất một lô và lấy tổng lớn nhất (ít âm nhất).

Đầu vào

• Dòng đầu tiên chứa số nguyên $n$ — số lượng lô đất ($1 \le n \le 10^5$).