Hiểu bài toán

Bài toán yêu cầu với mỗi chỉ số i từ 1 đến n của một mảng A gồm n số nguyên, tìm giá trị lớn nhất trong mảng A tại các vị trí từ i+1 đến n (phần tử bên phải của A[i]). Nếu không có phần tử nào bên phải (tức i = n), giá trị trả về là -1. Nói cách khác, với mỗi phần tử A[i], ta cần tìm giá trị lớn nhất ở phần đuôi mảng bắt đầu từ A[i+1].

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

Cách Duyệt ngược với cập nhật giá trị lớn nhất (Optimal)

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

const int maxN = 1e5 + 6;
int n, a[maxN], b[maxN];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    b[n] = -1;
    int max_right = -1;

    // Duyệt từ phải sang trái
    for(int i = n - 1; i >= 1; i--){
        max_right = a[i + 1]; // Hoặc có thể dùng max(max_right, a[i+1]) nhưng logic khác
        // Thực ra logic đúng của solution 1 là:
        // ans = max(ans, a[i+1]); b[i] = ans;
        // Tức là b[i] là max của đoạn (i+1...n)
    }

    // Code chuẩn hóa:
    b[n] = -1;
    int current_max = -1e9; // Hoặc một giá trị cực tiểu
    for(int i = n - 1; i >= 1; i--){
        current_max = max(current_max, a[i+1]);
        b[i] = current_max;
    }
    // Xử lý b[n] nếu cần là -1
    b[n] = -1;

    for(int i = 1; i <= n; i++) cout << b[i] << ' ';
    cout << '\n';
}

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

Đây là cách tiếp cận tối ưu nhất. Chỉ cần duyệt mảng một lần từ phải sang trái (từ n-1 về 1). Giả sử ta đã biết giá trị lớn nhất nằm trong đoạn từ i+2 đến n (lưu trong biến max_right), thì giá trị lớn nhất của đoạn (i+1...n) chính là max(max_right, a[i+1]). Sau khi tính xong b[i], ta cập nhật lại max_right để chuẩn bị cho bước tiếp theo. Cách này xử lý từng test case với độ phức tạp O(n) thời gian và O(n) bộ nhớ.

Cách Quy hoạch động cơ bản

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

ll n, t;
ll a[1000008];
ll b[1000008];
int main()
{
    freopen("tallest.inp","r",stdin);
    freopen("tallest.out","w",stdout);
    cin >> t;
    for (ll z = 1; z <= t; z++) {
        cin >> n;
        for (ll i = 1; i <= n; i++) cin >> a[i];
        b[n] = -1;
        b[n-1] = a[n];
        for (ll i = n-2; i >= 1; i--) 
            b[i] = max(b[i+1], a[i+1]);
        for (ll i = 1; i <= n; i++) cout << b[i] << " ";
        cout << endl;
    }
}

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

Cách tiếp cận này sử dụng quy hoạch động. Mảng b được dùng để lưu kết quả. Ta khởi tạo cơ sở: b[n] = -1 (vì không có phần tử bên phải) và b[n-1] = a[n]. Với các vị trí i từ n-2 về 1, giá trị b[i] (là max của đoạn i+1...n) được tính dựa trên b[i+1] (max của đoạn i+2...n) và a[i+1]. Công thức: b[i] = max(b[i+1], a[i+1]). Đây là một dạng điển hình của quy hoạch động từ dưới lên (bottom-up).

Cách Brute Force (Naive)

// Pseudo-code for illustration
void solve_naive() {
    int n; cin >> n;
    vector<int> a(n);
    for(auto &x : a) cin >> x;

    for(int i = 0; i < n; i++) {
        int max_val = -1;
        if (i == n - 1) {
            cout << -1 << " ";
            continue;
        }
        for(int j = i + 1; j < n; j++) {
            max_val = max(max_val, a[j]);
        }
        cout << max_val << " ";
    }
}

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

Đây là cách giải quyết trực quan nhất: Với mỗi phần tử tại vị trí i, duyệt qua tất cả các phần tử bên phải nó (từ i+1 đến n-1) để tìm giá trị lớn nhất. Tuy nhiên, độ phức tạp O(n^2) sẽ gây quá tải thời gian cho các n lớn (ví dụ n=10^5), dẫn đến lỗi Time Limit Exceeded. Phương pháp này chỉ khả thi với n rất nhỏ.

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

Bài học kinh nghiệm

• Vấn đề có tính chất 'vị trí tương đối' (từ i trở đi), rất phù hợp để giải quyết bằng cách duyệt ngược từ cuối mảng lên đầu mảng.
• Giá trị tại vị trí i phụ thuộc hoàn toàn vào các vị trí sau nó, cho phép áp dụng Quy hoạch động (Dynamic Programming) hoặc cách tiếp cận 'cửa sổ trượt' (Sliding Window) từ phải sang trái.

Lỗi thường gặp

• Xử lý sai trường hợp i = n (phần tử cuối cùng), thường bị nhầm lẫn giữa việc in -1 hay in giá trị của phần tử đó.
• Logic cập nhật biến lưu giá trị lớn nhất (max_right) bị sai nếu viết sai thứ tự gán giá trị, ví dụ gán b[i] = max(b[i], a[i+1]) trong một vòng lặp đơn giản mà không có biến phụ.