Hiểu bài toán

Bài toán yêu cầu tìm giá trị lớn nhất trong một mảng gồm n số nguyên (1 ≤ n ≤ 10^6). Dữ liệu đầu vào bao gồm số phần tử n và n số nguyên của mảng. Với ràng buộc n lên tới 10^6, giải thuật phải có độ phức tạp thời gian tuyến tính O(n) để chạy trong thời gian cho phép.

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

Cách Duyệt đơn giản (Simple Traversal)

#include <stdio.h>

int main(){
    int n;
    scanf("%d", &n);
    int max_val;
    // Đọc phần tử đầu tiên để khởi tạo max
    scanf("%d", &max_val);

    for(int i = 1; i < n; i++){
        int x;
        scanf("%d", &x);
        if(x > max_val) max_val = x;
    }
    printf("%d", max_val);
    return 0;
}

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

Phương pháp này chỉ lưu giữ biến giá trị lớn nhất (maxval) và duyệt qua các phần tử của mảng một lần. Nó đọc từng số, so sánh với maxval và cập nhật nếu cần. Đây là cách hiệu quả nhất về bộ nhớ vì không cần lưu toàn bộ mảng.

Cách Lưu mảng vào bộ nhớ (Array Storage)

#include <stdio.h>

int main(){
    int n;
    scanf("%d", &n);
    int a[1000000]; // Mảng tĩnh hoặc dùng biến toàn cục

    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }

    int max = a[0];
    for(int i=1; i<n; i++){
        if(a[i] > max) max = a[i];
    }
    printf("%d", max);
    return 0;
}

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

Tiếp cận này đọc toàn bộ dữ liệu vào mảng trước, sau đó tìm max bằng một vòng lặp riêng biệt. Dù độ phức tạp thời gian vẫn là O(n), nó tốn bộ nhớ O(n) và thực hiện hai vòng lặp (một để nhập, một để xử lý).

Cách Sử dụng hàm h hỗ trợ (fmax)

#include <stdio.h>
#include <math.h>

int main(){
    int n;
    scanf("%d", &n);
    int max_val = -1e9; // Khởi tạo giá trị âm lớn
    int x;

    for(int i=0; i<n; i++){
        scanf("%d", &x);
        max_val = fmax(x, max_val);
    }
    printf("%d", max_val);
    return 0;
}

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

Sử dụng hàm fmax từ thư viện math.h để cập nhật giá trị lớn nhất. Cần chú ý khởi tạo max_val đủ nhỏ (ví dụ -1e9) để đảm bảo giá trị thực sự lớn nhất được ghi nhận ngay từ phần tử đầu tiên.

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

Bài học kinh nghiệm

• Với n ≤ 10^6, ta cần thuật toán O(n) và không được dùng O(n^2).
• Không cần lưu toàn bộ mảng nếu chỉ cần tìm max, duyệt từng phần tử và so sánh là đủ.
• Phải xử lý đúng giá trị khởi tạo của biến max để tránh sai lệch với dữ liệu âm.

Lỗi thường gặp

• Khởi tạo max = 0 hoặc 1 sai nếu mảng chỉ chứa số âm (ví dụ: [-5, -2, -10]). Nên dùng phần tử đầu tiên hoặc giá trị âm rất nhỏ.
• Dùng mảng cỡ cố định (ví dụ 100000) có thể gây lỗi bộ nhớ nếu n > 100000. Nên dùng biến n xác định hoặc mảng động/toàn cục lớn.
• Quên kiểm tra n = 0 (trong đề bài n ≥ 1 nên không cần, nhưng trong thực hành cần kiểm tra).