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

View as PDF
Submit solution
Points: 0.21 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Bai` nay Hieu add day nhe ^^
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.