Hiểu bài toán

Bài toán yêu cầu tìm chỉ số của phần tử có giá trị lớn nhất trong một mảng số nguyên. Chỉ số được tính bắt đầu từ 0. Nếu có nhiều phần tử có cùng giá trị lớn nhất, cần trả về chỉ số lớn nhất trong số các chỉ số đó. Input bao gồm số lượng phần tử n và mảng n số nguyên. Giới hạn n ≤ 10^6 và giá trị phần tử ≤ 10^9.

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

Cách Duyệt một lần (One-pass Traversal)

#include <stdio.h>
#include <limits.h>

int main() {
    int n;
    scanf("%d", &n);
    int max_val = INT_MIN;
    int max_idx = -1;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (x >= max_val) {
            max_val = x;
            max_idx = i;
        }
    }
    printf("%d", max_idx);
    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. Chúng ta đọc mảng từng phần tử một, vừa đọc vừa cập nhật giá trị lớn nhất (maxval) và chỉ số tương ứng (maxidx). Điều kiện x >= max_val đảm bảo rằng nếu gặp giá trị bằng giá trị lớn nhất hiện tại, chỉ số mới (lớn hơn) sẽ được ghi đè, thỏa mãn yêu cầu trả về chỉ số lớn nhất khi có trùng lặp. Không cần lưu mảng vào bộ nhớ.

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

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[1000000]; // Kích thước cố định lớn, hoặc dùng malloc cho n lớn
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int max_idx = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] >= a[max_idx]) {
            max_idx = i;
        }
    }
    printf("%d", max_idx);
    return 0;
}

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

Phương pháp này đọc toàn bộ dữ liệu vào một mảng trong bộ nhớ trước, sau đó duyệt mảng để tìm chỉ số lớn nhất. Cách này tốn bộ nhớ hơn (O(n)) nhưng linh hoạt hơn nếu cần thực hiện nhiều thao tác khác trên mảng sau đó. Tuy nhiên, với bài toán chỉ cần tìm max, nó không tối ưu bằng cách duyệt trực tiếp.

Cách Sử dụng hàm phân tách (Modular Approach)

#include <stdio.h>

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

int chi_so_max(int a[], int n) {
    int max = a[0];
    int index = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > max) {
            max = a[i];
            index = i;
        } else if (a[i] == max) {
            if (i > index) index = i;
        }
    }
    return index;
}

int main() {
    int n, a[1000000];
    scanf("%d", &n);
    nhap(a, n);
    printf("%d", chi_so_max(a, n));
    return 0;
}

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

Cách tiếp cận này chia logic thành các hàm con (nhap, chi_so_max). Logic tìm max xử lý riêng trường hợp trùng lặp giá trị. Đây là cách viết có cấu trúc tốt (structured programming) nhưng về bản chất thuật toán vẫn là O(n) và tốn bộ nhớ O(n) do lưu mảng.

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

Bài học kinh nghiệm

• Yêu cầu 'chỉ số lớn nhất' khi có nhiều phần tử bằng nhau có thể được giải quyết bằng cách cập nhật chỉ số mới khi giá trị hiện tại lớn hơn HOẶC BẰNG (>=) giá trị lớn nhất hiện tại.
• Với giới hạn n ≤ 10^6, việc không lưu mảng mà chỉ dùng biến tạm là tối ưu nhất về bộ nhớ (O(1) space).

Lỗi thường gặp

• Sử dụng giá trị khởi tạo cho max quá nhỏ hoặc không đúng cách (ví dụ dùng -1 nhưng giá trị mảng có thể âm). Nên dùng INT_MIN hoặc khởi tạo bằng phần tử đầu tiên.
• Việc khai báo mảng cỡ lớn int a[n] hoặc int a[1000000] trong hàm main có thể gây tràn stack (Stack Overflow) trên một số hệ thống hoặc trình biên dịch nhất định. Giải pháp an toàn là dùng cấp phát bộ nhớ động malloc hoặc biến global.