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

Nguồn đề bài: http://vn.spoj.com/problems/GSS/

1. Đề bài GSS SPOJ

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

2. Thuật toán GSS SPOJ

Dùng cây IT với mỗi nút r ta sẽ lưu 4 giá trị: đoạn con có tổng lớn nhất bên trái(left), bên phải (right), tổng của các phần tử của cây con nút r (sum), tổng đoạn con lớn nhất (ans).

Để khởi tạo được những giá trị này ta có công thức như sau:

Sau khi đã tính đc như trên,với mỗi truy vấn q(x,y): nếu nút r đang xét nằm gọn trong khoảng cần tìm thì trả về cả 1 cặp 4 phần tử (left,right,sum,ans). Nếu hoàn toàn nằm ngoài khoảng đang xét thì trả về sum=0, left=right=ans=-oo;

Trường hơp còn lại thì trả về giá trị lớn nhất hơp bởi 2 nút con.kết quả cần in ra chính là it[r].ans;

Mình nói hơi kho hiểu, có gì thắc mắc các bạn để lại cmt phía dưới, mình sẽ giải đáp cho nhé.

3. Code tham khảo GSS SPOJ

2 thoughts on “GSS SPOJ – Đoạn con có tổng lớn nhất

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *