Hiểu bài toán

Bài toán yêu cầu tìm độ dài dãy con liên tiếp có giá trị trung bình lớn nhất. Tuy nhiên, dựa trên các giải pháp đã nộp, có thể thấy giá trị trung bình lớn nhất của một dãy con chỉ có thể đạt được khi tất cả các phần tử trong dãy con đó bằng nhau và bằng giá trị lớn nhất trong toàn bộ dãy. Nếu một dãy con chứa bất kỳ phần tử nào nhỏ hơn giá trị lớn nhất, giá trị trung bình của dãy con đó sẽ nhỏ hơn giá trị lớn nhất. Do đó, bài toán quy về việc tìm dãy con liên tiếp dài nhất mà tất cả các phần tử đều bằng giá trị lớn nhất của toàn mảng.

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

Cách Brute Force (Duyệt tất cả các dãy con)

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

int main() {
    int N;
    cin >> N;
    vector<long long> a(N);
    long long mx = -1e18;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (a[i] > mx) mx = a[i];
    }

    int maxLen = 0;
    // Duyệt tất cả các dãy con
    for (int i = 0; i < N; i++) {
        long long sum = 0;
        for (int j = i; j < N; j++) {
            sum += a[j];
            int len = j - i + 1;
            // Kiểm tra điều kiện trung bình == max
            if (sum == mx * len) {
                if (len > maxLen) maxLen = len;
            }
        }
    }
    cout << maxLen;
    return 0;
}

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

Cách tiếp cận này thử tất cả các dãy con con có thể có (từ i đến j). Với mỗi dãy con, nó tính tổng và kiểm tra xem trung bình của dãy con đó có bằng giá trị lớn nhất của toàn mảng hay không. Nếu bằng thì cập nhật độ dài lớn nhất. Phương pháp này đúng nhưng quá chậm cho dữ liệu lớn.

Cách Duyệt tối ưu dựa trên tính chất toán học

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

int main() {
    // Tối ưu tốc độ nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("average.inp", "r", stdin);
    freopen("average.out", "w", stdout);

    int N;
    cin >> N;
    vector<long long> a(N);

    // Tìm giá trị lớn nhất trong mảng
    long long mx = -1e18;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (a[i] > mx) mx = a[i];
    }

    // Duyệt một lần để tìm dãy liên tiếp các số bằng mx có độ dài lớn nhất
    int maxLen = 0;
    int currentLen = 0;
    for (int i = 0; i < N; i++) {
        if (a[i] == mx) {
            currentLen++;
            if (currentLen > maxLen) maxLen = currentLen;
        } else {
            currentLen = 0;
        }
    }

    cout << maxLen;
    return 0;
}

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

Đây là giải pháp tối ưu. Ta nhận thấy rằng để trung bình một dãy con bằng giá trị lớn nhất (mx), tất cả các phần tử trong dãy con đó phải bằng mx. Nếu có bất kỳ phần tử nào nhỏ hơn mx, trung bình sẽ giảm. Do đó, bài toán chỉ cần tìm dãy con liên tiếp dài nhất mà mọi phần tử đều bằng mx. Ta duyệt qua mảng một lần, đếm độ dài dãy liên tiếp các số bằng mx và cập nhật độ dài lớn nhất.

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

Bài học kinh nghiệm

• Giá trị trung bình lớn nhất của một dãy con bất kỳ không thể vượt quá giá trị lớn nhất của các phần tử trong dãy gốc (Max).
• Để một dãy con có giá trị trung bình bằng Max, tất cả các phần tử trong dãy con đó phải bằng Max.

Lỗi thường gặp

• Sử dụng biến kiểu int để lưu tổng hoặc giá trị lớn nhất có thể gây tràn số (overflow) nếu giá trị phần tử lớn.
• Quên xử lý trường hợp mảng rỗng hoặc kết quả trả về.