Hiểu bài toán

Cho một mảng gồm n số nguyên a[1], a[2], ..., a[n]. Nhiệm vụ của bạn là tìm độ dài dãy con liên tiếp dài nhất có tổng bằng 0. Nếu không có dãy con nào có tổng bằng 0, in ra 0.

Ví dụ: Input: n = 5, mảng a = [4, -2, 3, -2, 1] Output: 3 Giải thích: Dãy con từ chỉ số 2 đến 4 (-2, 3, -2) có tổng bằng -2 + 3 - 2 = -1? Đợi đã, tổng là -2 + 3 - 2 = -1. Dãy con từ chỉ số 1 đến 2: 4 -2 = 2. Dãy con từ chỉ số 3 đến 4: 3 - 2 = 1. Dãy con từ chỉ số 2 đến 5: -2 + 3 - 2 + 1 = 0. Độ dài là 4.

Ví dụ khác: Input: n = 6, mảng a = [1, -1, 2, -2, 3, -3] Output: 6

Input: n = 3, mảng a = [1, 2, 3] Output: 0

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

Cách Brute Force (Tử số)

// Tính tổng các dãy con và kiểm tra tổng có bằng 0 hay không
// Duyệt qua tất cả các cặp (i, j) để tìm tổng a[i]...a[j]
// Nếu tổng bằng 0, cập nhật độ dài lớn nhất là j - i + 1

#include <iostream>
#include <vector>
using namespace std;

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

    int max_len = 0;
    // Duyệt tất cả các điểm đầu
    for(int i = 0; i < n; i++) {
        long long sum = 0;
        // Duyệt tất cả các điểm cuối từ i trở đi
        for(int j = i; j < n; j++) {
            sum += a[j];
            if(sum == 0) {
                max_len = max(max_len, j - i + 1);
            }
        }
    }
    cout << max_len;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là cách tiếp cận trực quan nhất. Ta duyệt qua tất cả các vị trí bắt đầu i của dãy con. Với mỗi i, ta duyệt qua tất cả các vị trí kết thúc j (j >= i), tính tổng của dãy con a[i]...a[j] và kiểm tra xem tổng đó có bằng 0 hay không. Nếu bằng 0, ta cập nhật độ dài lớn nhất tìm được.

Cách này đảm bảo tìm được kết quả chính xác nhưng rất chậm do phải xét O(n^2) dãy con.

Cách Hash Map (Prefix Sum)

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

int main() {
    // Tối ưu hóa nhập xuất
    ios_base::sync_with_stdio(0); cin.tie(0);

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

    // Map lưu chỉ số xuất hiện đầu tiên của tổng tiền tố
    map<long long, int> first_occurrence;

    long long prefix_sum = 0;
    int max_len = 0;

    // Khởi tạo tổng tiền tố bằng 0 tại vị trí -1 (tức là trước mảng)
    // Việc này xử lý trường hợp dãy con bắt đầu từ index 0 có tổng bằng 0
    // Hoặc dãy con từ đầu đến hiện tại có tổng bằng 0
    first_occurrence[0] = -1;

    for(int i = 0; i < n; i++) {
        prefix_sum += a[i];

        // Nếu tổng tiền tố này đã xuất hiện trước đó
        if(first_occurrence.count(prefix_sum)) {
            // Độ dài dãy con là khoảng cách từ lần xuất hiện trước đến hiện tại
            // Ví dụ: tổng tại index 2 là 5, tổng tại index 5 là 5
            // Thì dãy con từ index 3 đến 5 có tổng bằng 0 (vì tổng tiền tố bị triệt tiêu)
            max_len = max(max_len, i - first_occurrence[prefix_sum]);
        } else {
            // Nếu chưa xuất hiện, lưu vị trí hiện tại
            first_occurrence[prefix_sum] = i;
        }
    }

    cout << max_len;
    return 0;
}

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

Sử dụng kỹ thuật Prefix Sum (Tổng tiền tố). Gọi S[i] là tổng các phần tử từ a[0] đến a[i]. Tổng của dãy con từ l đến r là S[r] - S[l-1].

Điều kiện dãy con từ l đến r có tổng bằng 0 là S[r] - S[l-1] = 0, hay S[r] = S[l-1].

Như vậy, để tìm dãy con dài nhất, ta chỉ cần tìm hai chỉ số i và j sao cho S[i] = S[j] với j > i và (j - i) là lớn nhất.

Ta duyệt mảng, tính tổng tiền tố prefix_sum. Dùng một map để lưu lại chỉ số (index) mà mỗi giá trị tổng tiền tố xuất hiện lần đầu tiên.

• Nếu prefix_sum đã có trong map, nghĩa là đã có một tổng bằng nó tại index idx. Khi đó dãy con từ idx + 1 đến i có tổng bằng 0. Ta cập nhật độ dài lớn nhất là i - idx.
• Nếu prefix_sum chưa có trong map, ta lưu lại index hiện tại i.

Độ phức tạp: O(n log n) do dùng map (hoặc O(n) nếu dùng unordered_map).

Cách Hash Map Optimization (Tối ưu)

#include "bits/stdc++.h"
#define N 1000001
#define ll long long
using namespace std;
ll a[N], i, s, m = 0, n;
map<ll, ll> f;
int main() {
    ifstream cin("zero.inp");
    ofstream cout("zero.out");
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];

    // Duyệt mảng từ 1 đến n
    for (i = 1; i <= n; i++) {
        s += a[i]; // s là tổng tiền tố tại i

        // Trường hợp đặc biệt: Tổng tiền tố tại i bằng 0
        // Tức là dãy con từ 1 đến i có tổng bằng 0
        if (s == 0 && n > 3e3) // Kiểm tra điều kiện n > 3000 có vẻ thừa nếu chỉ giải quyết bài toán tổng quát
            m = max(m, i);
        else {
            // Kiểm tra xem tổng s đã xuất hiện chưa
            if (f[s] == 0) 
                f[s] = i; // Lưu chỉ số xuất hiện đầu tiên (1-based index)
            else 
                m = max(m, i - f[s]); // Nếu đã xuất hiện, cập nhật độ dài
        }
    }
    cout << m;
    return 0;
}

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

Đây là biến thể của phương pháp Hash Map, sử dụng mảng f (hoặc map) để lưu chỉ số xuất hiện đầu tiên của tổng tiền tố.

Logic tương tự như trên:

1. Duyệt i từ 1 đến n, cập nhật tổng tiền tố s.
2. Nếu s == 0, nghĩa là dãy con từ đầu (1) đến i có tổng bằng 0. Độ dài là i. Cập nhật m.
3. Nếu s khác 0:
   • Nếu f[s] chưa được gán (giả sử giá trị mặc định là 0), lưu f[s] = i (lưu vị trí đầu tiên tổng này xuất hiện).
   • Nếu f[s] đã có giá trị (khác 0), nghĩa là tổng s đã xuất hiện tại vị trí f[s]. Khi đó, dãy con từ f[s] + 1 đến i có tổng bằng 0. Độ dài là i - f[s]. Cập nhật m.

Lưu ý: Code gốc có dòng if (s == 0 && n > 3e3) m = max(m, i);. Trong logic chung, nếu s == 0, độ dài là i. Nếu f được khởi tạo mặc định là 0, việc xử lý s == 0 có thể gộp vào logic chung nếu ta coi chỉ số 0 là điểm xuất phát (index 0). Tuy nhiên, code gốc dùng index 1-based và map nên cách xử lý này cũng hợp lý (vì f[0] mặc định là 0, i - 0 chính là i). Dòng điều kiện n > 3e3 có thể là một cách 'hack' để xử lý riêng bài toán nào đó, nhưng về tổng quát thì logic m = max(m, i) là đúng nếu s == 0.

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

Bài học kinh nghiệm

• Bài toán quy về bài toán tìm hai chỉ số i, j sao cho tổng tiền tố tại i bằng tổng tiền tố tại j (S[i] = S[j]).
• Sử dụng Hash Map (hoặc Dictionary) để lưu trữ các tổng tiền tố đã xuất hiện và chỉ số của chúng giúp giảm độ phức tạp từ O(n^2) xuống O(n log n) hoặc O(n).
• Xử lý trường hợp tổng tiền tố bằng 0 ngay từ đầu (index 0 hoặc -1) để đảm bảo dãy con bắt đầu từ phần tử đầu tiên được tính đến.

Lỗi thường gặp

• Lỗi kiểu dữ liệu: Tổng tiền tố có thể vượt quá giới hạn của int, cần dùng long long.
• Lỗi chỉ số (Indexing): Khi sử dụng map, cần chú ý giữa index 0-based và 1-based để tính độ dài chính xác. Nếu f[s] lưu index i (1-based) thì độ dài là i - f[s]. Nếu f[s] lưu index i (0-based) thì độ dài là i - f[s].
• Trường hợp tổng tiền tố bằng 0: Cần lưu sẵn tổng 0 tại chỉ số 0 (hoặc -1) để dãy con từ đầu đến điểm mà tổng tiền tố bằng 0 được tính chính xác.
• Hiệu năng: Nếu dùng std::map sẽ tốn O(log n) mỗi truy vấn. Trong một số ngôn ngữ hoặc thư viện, có thể dùng hash map (ở C++ là std::unordered_map) để đạt O(1) trung bình, nhưng cần chú ý dữ liệu đầu vào.