IDP0105A
Cho dãy số nguyên gồm 𝑁 phần tử 𝑎1, 𝑎2, … , 𝑎𝑁.
Định nghĩa dãy con của một dãy số là dãy sau khi bỏ đi một vài phần tử (hoặc không bỏ phần tử
nào). Ví dụ [3,2,5] là dãy con của dãy [3,5,2,9,5].
Dãy rỗng (không có phần tử nào) là dãy con của mọi dãy số, dãy rỗng thì có tổng bằng 0.
Yêu cầu: Gồm 𝑄 truy vấn, mỗi truy vấn gồm một cặp số (𝐿, 𝑅) (1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁). Với mỗi truy
vấn, bạn hãy tìm dãy con của dãy [𝑎𝐿
, 𝑎𝐿+1, … , 𝑎𝑅
] và có tổng lớn nhất, bạn hãy in ra giá trị đó.
Input:
Dòng đầu chứa hai số nguyên dương 𝑁 và 𝑄 (𝑄, 𝑁 ≤ 105);
Dòng thứ hai chứa số nguyên 𝑎1, 𝑎2, … , 𝑎𝑁 (|𝑎𝑖
| ≤ 105);
𝑄 dòng sau, mỗi dòng là một cặp số nguyên dươn (𝐿,𝑅) (1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁).
Output: Gồm 𝑄 dòng, mỗi dòng là kết quả bài toán tương ứng với cặp (𝐿, 𝑅).
Ví dụ:
IDP0105A.INP IDP0105A.OUT
5 2
-1 2 -3 4 -5
2 4
3 3
6
0
c++ help mik
Loga
Sinh Học lớp 12
