Hiểu bài toán

Bài toán yêu cầu tìm tổng lớn nhất của một dãy con trong một đoạn [L, R] của dãy ban đầu. Dãy con được tạo ra bằng cách bỏ đi một số phần tử (không nhất thiết liền kề) hoặc giữ nguyên. Dãy rỗng có tổng bằng 0. Với các ràng buộc n, q ≤ 10^5, giải pháp duyệt tất cả các dãy con (2^n) là không thể chấp nhận được.

Các cách tiếp cận

Cách Brute Force

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    while (q--) {
        int L, R;
        cin >> L >> R;
        long long tong = 0;
        for (int i = L - 1; i <= R - 1; i++) {
            if (a[i] > 0) tong += a[i];
        }
        cout << tong << endl;
    }
    return 0;
}

• Time Complexity: O(n * q)
• Space Complexity: O(n)

Giải pháp này xử lý từng truy vấn một cách độc lập. Với mỗi truy vấn [L, R], nó duyệt qua tất cả các phần tử từ chỉ số L-1 đến R-1. Nếu phần tử đó dương, nó được cộng vào tổng. Đây là cách tiếp cận trực quan nhất để giải quyết bài toán con dãy con có tổng lớn nhất (Maximum Subarray Sum) khi các phần tử âm bị bỏ qua và dương được giữ lại.

Cách Prefix Sum (Tổng tiền tố)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Xử lý logic: chỉ cộng các số dương
    // Tạo mảng mới chỉ chứa số dương, âm chuyển thành 0
    vector<long long> b(n);
    for (int i = 0; i < n; i++) {
        b[i] = (a[i] > 0) ? a[i] : 0;
    }

    // Tính mảng tổng tiền tố (Prefix Sum)
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + b[i];
    }

    while (q--) {
        int L, R;
        cin >> L >> R;
        // Truy vấn tổng trong đoạn [L, R] bằng cách lấy hiệu 2 đầu
        cout << pref[R] - pref[L - 1] << "\n";
    }

    return 0;
}

• Time Complexity: O(n + q)
• Space Complexity: O(n)

Đây là giải pháp tối ưu hóa cho các truy vấn lặp lại. Thay vì duyệt lại mảng mỗi lần, ta tiền xử lý mảng bằng cách:

1. Tạo một mảng trung gian chứa các số dương của mảng ban đầu (số âm thay bằng 0).
2. Tính mảng tổng tiền tố (Prefix Sum) cho mảng này. Với mỗi truy vấn [L, R], tổng lớn nhất của dãy con nằm trong đoạn này chính là tổng của tất cả các số dương trong đoạn đó. Ta có thể tính nhanh bằng cách lấy pref[R] - pref[L-1]. Độ phức tạp thời gian giảm từ O(n*q) xuống O(n + q).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán 'Dãy con có tổng lớn nhất' (Maximum Subarray Sum) khi chỉ được chọn các phần tử dương (và không cần tính chỉ số bắt đầu/kết thúc) thực chất là bài toán tính tổng các phần tử dương trong đoạn [L, R].
• Bằng cách chuyển các phần tử âm thành 0, bài toán truy vấn đoạn [L, R] trở thành bài toán tính tổng tiền tố (Prefix Sum) trên mảng mới.
• Giải pháp O(n*q) quá chậm cho n, q lên tới 10^5, cần chuyển sang O(n + q) bằng tiền xử lý.

Lỗi thường gặp

• Lỗi type: Tổng các số dương có thể vượt quá giới hạn của int (nếu tổng > 2*10^9). Cần sử dụng long long cho biến tổng và mảng tổng tiền tố.
• Lỗi index: Khi tính tổng tiền tố, cần chú ý khoảng cách chỉ số. Ví dụ pref[R] - pref[L-1] (nếu dùng mảng 1-indexed) hoặc pref[R+1] - pref[L] (nếu dùng mảng 0-indexed).
• Xử lý số âm: Đừng chỉ cộng số dương vào tổng, hãy thiết lập giá trị mảng trung gian bằng 0 nếu phần tử âm để đảm bảo công thức tổng tiền tố hoạt động chính xác.