Đ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:
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
bài này bắt buộc phải chọn ít nhất một ptu của dãy nha mn
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài tương tự: https://codeforces.com/contest/1567/problem/E