Ý tưởng giải quyết bài toán

Để bài toán chạy hiệu quả với ~ N \leq 10^6 ~, chúng ta sử dụng prefix sum kết hợp với hashmap.

Cách tiếp cận

1. Prefix Sum:

   • Sử dụng mảng tổng tích lũy ~ prefixSum[i] ~: ~ prefixSum[i] = A[0] + A[1] + \dots + A[i] ~
   • Tổng của đoạn ~ A[l] ~ đến ~ A[r] ~ là: ~ sum(l, r) = prefixSum[r] - prefixSum[l-1] ~
   • Tổng này bằng ~ 0 ~ nếu: ~ prefixSum[r] = prefixSum[l-1] ~

2. Lưu trữ trạng thái:

   • Dùng hashmap ~ sumIndex ~ để lưu vị trí đầu tiên mỗi giá trị của ~ prefixSum[i] ~ xuất hiện.
   • Nếu tại vị trí ~ i ~, giá trị ~ prefixSum[i] ~ đã xuất hiện trong ~ sumIndex ~ tại vị trí ~ j ~:
     • Đoạn ~ [j+1, i] ~ có tổng bằng ~ 0 ~.

3. Duyệt và tính toán:

   • Duyệt qua mảng, tính ~ prefixSum[i] ~ và kiểm tra trong ~ sumIndex ~.
   • Nếu ~ prefixSum[i] ~ đã tồn tại, tính độ dài đoạn ~ [j+1, i] ~ và cập nhật độ dài lớn nhất.

Độ phức tạp

• Thời gian: ~ O(N) ~, do duyệt qua mảng một lần và sử dụng hashmap để tra cứu giá trị.
• Không gian: ~ O(N) ~, lưu trữ các giá trị ~ prefixSum ~ trong hashmap.

C++ Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // Nhập N
    int N;
    cin >> N;

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Sử dụng prefix sum và hashmap
    unordered_map<int, int> sumIndex; // Lưu vị trí xuất hiện đầu tiên của prefixSum
    sumIndex[0] = -1; // Tổng bằng 0 trước bất kỳ phần tử nào

    int prefixSum = 0, maxLength = -1;

    for (int i = 0; i < N; ++i) {
        prefixSum += A[i];

        // Kiểm tra nếu tổng này đã xuất hiện
        if (sumIndex.find(prefixSum) != sumIndex.end()) {
            // Tính độ dài đoạn con
            maxLength = max(maxLength, i - sumIndex[prefixSum]);
        } else {
            // Nếu chưa tồn tại, lưu vị trí hiện tại
            sumIndex[prefixSum] = i;
        }
    }

    // In kết quả
    cout << (maxLength == -1 ? -1 : maxLength) << "\n";

    return 0;
}

Giải thích chương trình

1. Khởi tạo:

   • Nhập dữ liệu mảng.
   • Khởi tạo ~ sumIndex[0] = -1 ~ để xử lý trường hợp mảng con bắt đầu từ đầu mảng.

2. Tính toán Prefix Sum:

   • Duyệt qua mảng và tính ~ prefixSum[i] ~ tại mỗi bước.
   • Nếu ~ prefixSum[i] ~ đã tồn tại trong ~ sumIndex ~:
     • Tính độ dài đoạn ~ [j+1, i] ~.
     • Cập nhật độ dài lớn nhất ~ maxLength ~.
   • Nếu chưa tồn tại, lưu vị trí vào ~ sumIndex ~.

3. Kết quả:

   • Nếu không tìm thấy mảng con nào có tổng bằng ~ 0 ~, in ra ~ -1 ~.
   • Ngược lại, in ra ~ maxLength ~.

Ví dụ

Input:

15
-4 1 2 -1 2 -3 8 -2 -8 7 -5 8

Output:

5

Giải thích:

• Dãy con dài nhất có tổng bằng ~ 0 ~ là ~ [1, 2, -1, 2, -4] ~, độ dài = 5.

Input:

5
1 2 -3 3 1

Output:

3

Giải thích:

• Dãy con dài nhất là ~ [1, 2, -3] ~, tổng = 0, độ dài = 3.

Input:

5
1 2 3 4 5

Output:

-1

Giải thích:

• Không tồn tại dãy con nào có tổng bằng ~ 0 ~.