Hướng dẫn giải

1. Phân tích bài toán

Ta cần chọn ba phần tử lớn nhất, không yêu cầu chúng phải có giá trị khác nhau. Ví dụ, dãy 7 7 2 1 có kết quả 7 7 2.

Vì ~n~ có thể lên tới ~10^5~, có thể sắp xếp dãy rồi lấy ba phần tử cuối. Tuy nhiên, bài toán cũng có thể giải bằng một lần duyệt, không cần lưu toàn bộ dãy.

2. Ý tưởng thuật toán

Dùng ba biến a, b, c lần lượt lưu số lớn nhất, lớn thứ hai và lớn thứ ba trong các phần tử đã đọc, luôn đảm bảo ~a \ge b \ge c~.

Ban đầu, đặt cả ba biến bằng một giá trị nhỏ hơn mọi phần tử hợp lệ, chẳng hạn -100001.

Với mỗi số ~x~ đọc được:

1. Nếu ~x \ge a~: đẩy b xuống c, đẩy a xuống b, rồi gán a = x.
2. Ngược lại, nếu ~x \ge b~: đẩy b xuống c, rồi gán b = x.
3. Ngược lại, nếu ~x > c~: gán c = x.
4. Nếu không thuộc các trường hợp trên, bỏ qua ~x~.

Sau khi đọc đủ ~n~ phần tử, in a b c.

3. Minh họa

Với dãy 2 1 3 5 4:

Kết quả: 5 4 3.

4. Code C++ mẫu

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

int n, x, a = -100001, b = -100001, c = -100001;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        if (x >= a)
        {
            c = b;
            b = a;
            a = x;
        }
        else if (x >= b)
        {
            c = b;
            b = x;
        }
        else if (x > c)
        {
            c = x;
        }
    }
    cout << a << " " << b << " " << c << endl;
    return 0;
}

5. Độ phức tạp

• Thời gian: ~O(n)~, vì mỗi phần tử được xét đúng một lần.
• Bộ nhớ phụ: ~O(1)~, vì chỉ dùng một số biến, không cần mảng.

6. Lưu ý

• Không loại bỏ các giá trị trùng nhau: nếu số lớn nhất xuất hiện nhiều lần thì vẫn được tính là nhiều phần tử.
• Dãy có thể chứa số âm: không khởi tạo a, b, c bằng 0.
• Sau mỗi lần cập nhật, phải giữ đúng thứ tự ~a \ge b \ge c~.
• Không cần sắp xếp toàn bộ dãy để tìm ba số lớn nhất.