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
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 ^^