Hiểu bài toán

Cho một dãy số nguyên $A$ gồm $N$ phần tử. Tìm độ dài lớn nhất của một đoạn con liên tiếp có tổng các phần tử không âm (tức là tổng >= 0). Nếu không tồn tại đoạn con nào thỏa mãn, in ra -1.

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

Cách Brute Force (Tử dãy)

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int res = 0;
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += a[j];
            if (sum >= 0) {
                res = max(res, j - i + 1);
            }
        }
    }
    if (res == 0) cout << -1;
    else cout << res;
    return 0;
}

• Time Complexity: O(N^2)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Duyệt qua tất cả các vị trí bắt đầu $i$ của đoạn con. Với mỗi $i$, duyệt qua tất cả các vị trí kết thúc $j \ge i$, tính tổng và cập nhật độ dài lớn nhất nếu tổng không âm. Với $N \le 10^5$, phương pháp này thực hiện khoảng $10^{10}$ phép tính, vượt quá giới hạn thời gian (thường là 1 giây).

Cách Prefix Sum và Sắp xếp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    vector<pair<long long, long long>> pref(n + 1);
    long long sum = 0;
    pref[0] = {0, 0};

    // Tính tổng tiền tố và lưu chỉ số
    for (int i = 1; i <= n; i++) {
        sum += a[i - 1];
        pref[i] = {sum, i};
    }

    // Sắp xếp các tổng tiền tố theo giá trị tăng dần
    sort(pref.begin(), pref.end());

    long long ans = -1, mn = 1e18;

    // Duyệt qua các tổng đã sắp xếp, giữ lại chỉ số nhỏ nhất đã gặp
    for (auto &p : pref) {
        long long idx = p.second;
        if (idx < mn) mn = idx;
        ans = max(ans, idx - mn);
    }

    if (ans <= 0) cout << -1;
    else cout << ans;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Sử dụng tổng tiền tố $P[i] = \sum{k=1}^i ak$. Tổng đoạn con từ $i$ đến $j$ là $P[j] - P[i-1]$. Điều kiện $P[j] - P[i-1] \ge 0$ tương đương với $P[i-1] \le P[j]$. Ta cần tìm $i-1$ và $j$ sao cho $P[i-1] \le P[j]$ và $j - (i-1)$ là lớn nhất. Bằng cách sắp xếp các cặp (giá trị tổng tiền tố, chỉ số), ta có thể duyệt qua các tổng đã sắp xếp. Khi gặp một tổng tại vị trí $j$, nếu trước đó đã gặp một tổng nhỏ hơn hoặc bằng tại vị trí $i-1$ nhỏ nhất, ta cập nhật kết quả. Phương pháp này hiệu quả hơn Brute Force nhưng vẫn chậm hơn phương pháp tối ưu.

Cách Monotonic Stack (Ngăn xếp đơn điệu)

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

#define int long long

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    // Tính tổng tiền tố
    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] + a[i];
    }
    // Xây dựng ngăn xếp chứa các chỉ số i sao cho p[i] giảm dần
    vector<int> st;
    for (int i = 0; i <= n; ++i) {
        if (st.empty() || p[i] < p[st.back()]) st.push_back(i);
    }
    int ans = 0;
    // Duyệt ngược từ cuối về đầu
    for (int j = n; j >= 0; --j) {
        while (!st.empty() && p[j] >= p[st.back()]) {
            ans = max(ans, j - st.back());
            st.pop_back();
        }
        if (st.empty()) break;
    }
    cout << (ans == 0 ? -1 : ans);
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là phương pháp tối ưu nhất.

1. Tính tổng tiền tố $P[k]$ với $P[0]=0$. Đặt $P[k]$ vào mảng.
2. Xây dựng một ngăn xếp chứa các chỉ số $i$ sao cho các giá trị $P[i]$ trong ngăn xếp tăng dần (từ đáy lên). Cụ thể, ta chỉ đẩy chỉ số $i$ vào ngăn xếp nếu $P[i] < P[st.back()]$. Điều này đảm bảo rằng nếu ta tìm được $j$ sao cho $P[j] \ge P[st.back()]$, thì $j - st.back()$ là độ dài lớn nhất có thể tính được với giá trị $P[st.back()]$ này (vì $st.back()$ là chỉ số nhỏ nhất có giá trị tổng như vậy).
3. Duyệt $j$ từ $n$ về $0$. Với mỗi $j$, ta kiểm tra ngăn xếp: nếu $P[j] \ge P[st.top()]$, điều này có nghĩa là đoạn con từ $st.top()$ đến $j$ có tổng không âm. Vì $j$ đang giảm dần, ta cập nhật độ dài $j - st.top()$ và loại bỏ $st.top()$ khỏi ngăn xếp (vì các $j$ nhỏ hơn sau này sẽ cho độ dài ngắn hơn). Phương pháp này đảm bảo mỗi phần tử được đẩy vào và lấy ra khỏi ngăn xếp tối đa 1 lần, đạt độ phức tạp tuyến tính.

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

Bài học kinh nghiệm

• Bài toán có thể chuyển đổi về bài toán tìm hai chỉ số $i, j$ sao cho tổng tiền tố $P[j] \ge P[i]$ và $j-i$ lớn nhất.
• Phương pháp Monotonic Stack dựa trên ý tưởng: với một giá trị tổng tiền tố $P[i]$ cố định, ta muốn tìm $j$ lớn nhất sao cho $P[j] \ge P[i]$ (với $j > i$).
• Ngăn xếp đơn điệu giúp loại bỏ các chỉ số không thể tối ưu hóa kết quả, giảm độ phức tạp từ $O(N^2)$ hoặc $O(N \log N)$ xuống $O(N)$.

Lỗi thường gặp

• Quên xử lý trường hợp không có đoạn con nào thỏa mãn (cần in -1).
• Lỗi tràn số khi tính tổng, cần sử dụng kiểu dữ liệu long long cho tổng tiền tố.
• Lầm tưởng giữa chỉ số của tổng tiền tố và chỉ số của phần tử trong mảng gốc (cần chú ý khoảng cách $j - i$).