Hiểu bài toán

Bài toán yêu cầu xử lý một dãy số gồm N phần tử. Với mỗi phần tử thứ i (từ 0 đến N-1) trong dãy, ta cần tính "điểm thưởng" bằng cách tìm số lớn nhất trong đoạn dãy từ đầu cho đến phần tử hiện tại (từ a[0] đến a[i]). Nếu phần tử hiện tại lớn hơn tất cả các phần tử trước nó, điểm thưởng chính là giá trị của nó; ngược lại, điểm thưởng bằng giá trị lớn nhất tìm được ở các bước trước. Nói cách khác, ta cần in ra dãy các giá trị max prefix (giá trị lớn nhất tiền tố) của dãy đầu vào.

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

Cách Duyệt tuần tự (Linear Scan)

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

int main() {
    freopen("bonus.inp", "r", stdin);
    freopen("bonus.out", "w", stdout);

    int k;
    cin >> k;
    long long maxVal = 0;

    for (int i = 0; i < k; i++) {
        long long a;
        cin >> a;
        if (a >= maxVal) {
            maxVal = a;
        }
        cout << maxVal << "\n";
    }

    return 0;
}

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

Đây là cách tiếp cận trực quan và hiệu quả nhất. Ta duy trì một biến lưu giá trị lớn nhất tìm được từ đầu đến hiện tại (maxVal). Với mỗi phần tử mới đọc vào:

1. So sánh nó với maxVal.
2. Nếu lớn hơn hoặc bằng, cập nhật maxVal = phần tử mới.
3. In ra maxVal. Cách này chỉ cần duyệt qua dãy số một lần duy nhất, sử dụng hằng số bộ nhớ.

Cách Sử dụng mảng phụ (Prefix Array)

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

int main() {
    freopen("BONUS.inp", "r", stdin);
    freopen("BONUS.out", "w", stdout);

    int N;
    cin >> N;
    vector<long long> a(N);
    long long currentMax = LLONG_MIN;

    for(int i = 0; i < N; i++) {
        cin >> a[i];
        if(a[i] > currentMax) currentMax = a[i];
        cout << currentMax << "\n";
    }

    return 0;
}

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

Cách này về cơ bản logic xử lý giống cách 1 (duyệt tuần tự), nhưng giải pháp tham khảo (Solution 3) có khai báo mảng vector<long long> a(N) để lưu trữ toàn bộ dãy số đầu vào trước. Mặc dù không cần thiết phải lưu cả mảng để giải bài toán này (vì chỉ cần xử lý luồng dữ liệu), nhưng đây là một cách tiếp cận phổ biến khi cần giữ lại dữ liệu cho các bước xử lý phức tạp hơn. Logic tính toán vẫn là duy trì currentMax và cập nhật.

Cách Phương pháp Brute-force (Không hiệu quả)

// Pseudo-code minh họa logic không tối ưu
// Đọc dữ liệu vào mảng A
for (int i = 0; i < N; i++) {
    long long maxVal = A[0];
    // Duyệt lại từ đầu để tìm max trong đoạn [0, i]
    for (int j = 0; j <= i; j++) {
        if (A[j] > maxVal) maxVal = A[j];
    }
    cout << maxVal << endl;
}

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

Đây là phương pháp naïve, không có trong các giải pháp đã submitting đúng (do TLE), nhưng là một bài học quan trọng. Với mỗi phần tử, ta lặp lại một vòng lặp từ đầu để tìm max. Nếu N lớn (ví dụ 10^5), độ phức tạp O(N^2) sẽ vượt quá giới hạn thời gian. Các giải pháp đã cho đều tránh né bẫy này.

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu giá trị max tiền tố (max prefix), không cần phải can thiệp vào mảng gốc sau khi đã đọc.
• Biến lưu trạng thái (maxVal) là chìa khóa để giảm độ phức tạp từ O(n^2) xuống O(n).
• Sử dụng long long là cần thiết nếu giá trị đầu vào có thể vượt quá giới hạn của int.

Lỗi thường gặp

• Lặp lồng nhau (nested loop) không cần thiết dẫn đến quá thời gian (TLE).
• Quên xử lý trường hợp số âm hoặc khởi tạo biến max sai (ví dụ nếu dãy chỉ toàn số âm, khởi tạo max = 0 là sai). Solution 3 dùng LLONG_MIN để xử lý an toàn cho mọi trường hợp.
• Lỗi file I/O: Quên freopen hoặc sai tên file ('bonus.inp'/'BONUS.inp') có thể gây ra lỗi runtime hoặc sai kết quả khi nộp bài trên các hệ thống thi đấu.