Hướng giải của Đoạn Con Tổng Lớn Nhất

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán tìm đoạn con liên tiếp có tổng lớn nhất nằm trong khoảng truy vấn \([L, R]\). Tại mỗi node của Segment Tree, ta quản lý thông tin phức hợp gồm:

  • sum: Tổng tất cả phần tử trong đoạn quản lý.
  • pref: Tổng đoạn con liên tiếp lớn nhất bắt đầu từ biên trái (tiền tố cực đại).
  • suff: Tổng đoạn con liên tiếp lớn nhất kết thúc tại biên phải (hậu tố cực đại).
  • ans: Tổng đoạn con liên tiếp lớn nhất nằm hoàn toàn trong đoạn quản lý.

Khi gộp thông tin của hai node con trái \(l\) và phải \(r\):

  • sum = l.sum + r.sum
  • pref = max(l.pref, l.sum + r.pref)
  • suff = max(r.suff, r.sum + l.suff)
  • ans = max({l.ans, r.ans, l.suff + r.pref}) (đoạn con tối ưu có thể nằm trọn ở con trái, con phải hoặc bắc ngang qua biên giới giữa hai con).

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long sum, pref, suff, ans;
};

Node combine(Node l, Node r) {
    Node res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suff = max(r.suff, r.sum + l.suff);
    res.ans = max({l.ans, r.ans, l.suff + r.pref});
    return res;
}

struct SegTree {
    int n; vector<Node> tree;
    SegTree(int size) { n = size; tree.assign(4 * n, {0, 0, 0, 0}); }
    void build(int node, int start, int end, const vector<int>& a) {
        if(start == end) {
            long long v = a[start];
            tree[node] = {v, max(0LL, v), max(0LL, v), max(0LL, v)};
            return;
        }
        int mid = (start + end)/2;
        build(2*node, start, mid, a);
        build(2*node+1, mid+1, end, a);
        tree[node] = combine(tree[2*node], tree[2*node+1]);
    }
    Node query(int node, int start, int end, int l, int r) {
        if(l <= start && end <= r) return tree[node];
        int mid = (start + end)/2;
        if(r <= mid) return query(2*node, start, mid, l, r);
        if(l > mid) return query(2*node+1, mid+1, end, l, r);
        return combine(query(2*node, start, mid, l, r), query(2*node+1, mid+1, end, l, r));
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; if(!(cin >> n >> q)) return 0;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    SegTree st(n);
    st.build(1, 0, n-1, a);
    while(q--){
        int l, r; cin >> l >> r;
        cout << st.query(1, 0, n-1, l-1, r-1).ans << "\n";
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.