GSS - Đoạn con có tổng lớn nhất
Giới hạn- Thời gian: 0.09s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho dãy số a[1], a[2], ..., a[n] (|a[i]| <= 15000, n <= 50000).
Hàm q(x, y) = max { tổng(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }.
Cho m câu hỏi dạng x, y (1 <= x <= y <= n). (m <= 50000) -> hãy tính các q(x, y).
Input
- Dòng đầu là n.
- Dòng thứ hai là dãy a.
- Dòng thứ 3 là m.
- m dòng tiếp theo mỗi dòng là 1 cặp số x, y.
Output
-> Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng.
Example
Input:
3
-1 2 3
1
1 2
Output:
2
- Người up: dtmp
- Nguồn bài: Bai` nay Hieu add day nhe ^^