Đoạn con có tổng lớn nhất

Xem dạng PDF
Gửi bài giải
Điểm: 0,21 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Bai` nay Hieu add day nhe ^^
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy số ~a_1~, ~a_2~, ..., ~a_n~ ~(|a_i| \le 15000, n \le 50000)~.

Hàm ~q(x, y)~ = ~max~ {tổng(~a_i~+~a_{i + 1}~+...+~a_j~), ~x \le i \le j \le y~ }.

Cho ~m~ câu hỏi dạng ~x~, ~y~ ~(1 \le x \le y \le n)~. ~(m \le 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 ra trên 1 dòng.

Sample Input

3
-1 2 3
1
1 2

Sample Output

2

Bình luận

Hãy đọc nội quy trước khi bình luận.