Tổng mảng con lớn nhất trong khoảng cho trước (Maximum Subarray Sum in Range) trong C++

Cho mảng số nguyên, tìm tổng lớn nhất của mảng con bất kỳ nằm hoàn toàn trong khoảng chỉ số [first, last].

Ví dụ

Đầu vào: arr[] = {3, 2, -1, 6, 7, 2}, first=0, last=5

Đầu ra: 19 (mảng con: 3, 2, -1, 6, 7, 2 → tổng 19)

Đầu vào: arr[] = {-2, 1, 3, 4, 8, 9, 23}, first=0, last=3

Đầu ra: 8 (mảng con: 1, 3, 4)

Phương pháp: Segment Tree lưu 4 giá trị

Mỗi nút lưu: max_val (tiền tố max), max_temp (hậu tố max), total (tổng đoạn), sub_sum (tổng mảng con max trong đoạn).

• Gộp 2 nút con: max_val = max(L.max_val, L.total + R.max_val), max_temp = max(R.max_temp, R.total + L.max_temp), total = L.total + R.total, sub_sum = max(L.sub_sum, R.sub_sum, L.max_temp + R.max_val).
• Xây cây O(N), truy vấn O(log N).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

struct Node {
    int max_val, max_temp, total, sub_sum;
    Node() : max_val(-INF), max_temp(-INF), total(-INF), sub_sum(-INF) {}
};

Node merge(Node L, Node R) {
    Node res;
    res.max_val = max(L.max_val, L.total + R.max_val);
    res.max_temp = max(R.max_temp, R.total + L.max_temp);
    res.total = L.total + R.total;
    res.sub_sum = max({L.sub_sum, R.sub_sum, L.max_temp + R.max_val});
    return res;
}

void build(Node *tree, int arr[], int l, int r, int idx) {
    if (l == r) {
        tree[idx].total = tree[idx].max_val = tree[idx].max_temp = tree[idx].sub_sum = arr[l];
        return;
    }
    int mid = (l+r)/2;
    build(tree, arr, l, mid, 2*idx);
    build(tree, arr, mid+1, r, 2*idx+1);
    tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
}

Node query(Node *tree, int l, int r, int ql, int qr, int idx) {
    if (ql > r || qr < l) return Node();
    if (ql <= l && r <= qr) return tree[idx];
    int mid = (l+r)/2;
    return merge(query(tree, l, mid, ql, qr, 2*idx),
                 query(tree, mid+1, r, ql, qr, 2*idx+1));
}

int main() {
    int arr[] = {3, 2, -1, 6, 7, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    Node *tree = new Node[4*n];
    build(tree, arr, 0, n-1, 1);
    int first=0, last=5;
    Node ans = query(tree, 0, n-1, first, last, 1);
    cout << "Maximum Subarray Sum in range: " << ans.sub_sum;
    return 0;
}

Đầu ra chương trình

Maximum Subarray Sum in a given Range is: 19