Bỏ qua đến nội dung

Hướng giải: MAXSUM

MAXSUM

Mã bài: prefix01 Nhóm: Uncategorized Điểm: 100 điểm
Giới hạn
1,0 s, 256 MB
Tỉ lệ AC
10,8%
Người giải
3
Chỉ đọc hướng giải khi bế tắc và đừng sao chép mã trong đó. Hãy tôn trọng người ra đề và người viết hướng giải: nộp lời giải chính thức khi chưa tự giải được bài có thể khiến bạn bị khóa tài khoản.

Nguồn: CSES

Gọi s(i) là tổng tiền tố x_1+x_2+...+x_i. Sử dụng hàm này, ta có thể tính tổng của bất kỳ đoạn con nào như sau:

\displaystyle x_j+x_{j+1}+...x_i=s(i)-s(j-1)

Để giải bài toán, ta duyệt qua mảng và duy trì một multiset chứa tất cả các tổng tiền tố s(k) thỏa mãn: i-b\le k \le i-a, trong đó i là vị trí hiện tại. Khi đó, tổng lớn nhất của một đoạn con kết thúc tại vị trí i là s(i)-s(k') với s(k') là tổng tiền tố nhỏ nhất trong multiset. Độ phức tạp: O(n.log(n)).

Ta cũng có thể xây dựng một lời giải hiệu quả hơn bằng cách sử dụng thuật toán tìm giá trị nhỏ nhất trên cửa sổ trượt trong thời gian tuyến tính, thay cho multiset. Ý tưởng là duy trì một dãy tăng dần các giá trị nằm trong cửa sổ hiện tại. Cách này sử dụng cấu trúc dữ liệu deque và có độ phức tạp O(n).

Tham khảo Bài toán tìm max-min trong đoạn tịnh tiến

Bình luận