Hiểu bài toán

Bài toán yêu cầu tìm chênh lệch lớn nhất giữa hai phần tử bất kỳ trong một mảng số nguyên cho trước. Nói cách khác, ta cần tìm hiệu số giữa giá trị lớn nhất và giá trị nhỏ nhất của mảng.

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

Cách Sắp xếp mảng

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0; 
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    int a[n];

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

    bubbleSort(a, n);
    int hieu = a[n-1] - a[0];
    printf("%d",hieu);
    return 0;
}

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

Cách tiếp cận này sử dụng thuật toán sắp xếp (Bubble Sort) để sắp xếp mảng tăng dần. Sau khi sắp xếp, phần tử đầu tiên là giá trị nhỏ nhất và phần tử cuối cùng là giá trị lớn nhất. Chênh lệch lớn nhất là hiệu của hai giá trị này. Tuy nhiên, Bubble Sort có độ phức tạp O(n^2), không hiệu quả cho n lớn (lên tới 10^4).

Cách Duyệt một lần (Tối ưu)

#include <stdio.h>
#include <math.h>
int main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    int min = 1e9, max = -1e9;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        min = fmin(min, a[i]);
        max = fmax(max, a[i]);
    }
    printf("%d", max - min);
}

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

Đây là phương pháp tối ưu nhất. Ta chỉ cần duyệt qua mảng một lần duy nhất. Trong quá trình duyệt, ta cập nhật liên tục giá trị nhỏ nhất (min) và giá trị lớn nhất (max) tìm được cho đến thời điểm hiện tại. Sau khi duyệt xong, chênh lệch lớn nhất chính là max - min. Độ phức tạp thời gian là O(n) và không gian là O(1).

Cách Duyệt một lần (Cơ bản)

#include <stdio.h>
void KhoangCachLonNhat () {
    int a[10000] ;
    int n ;
    scanf ("%d", &n) ;
    for (int i=0; i<n; i++) {
        scanf ("%d", &a[i]) ;
    }
    int min = a[0] ;
    int max = a[0] ;
    for (int i=1; i<n; i++) {

        if (a[i] < min) {
            min = a[i] ;
        }
        if (a[i] > max) {
            max = a[i] ;
        }
    }
    int KhoangCach = max - min ;
    printf ("%d", KhoangCach) ;
}

int main(void) {
    KhoangCachLonNhat () ;
    return 0;
}

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

Tương tự như phương pháp tối ưu, cách này cũng duyệt một lần để tìm min và max. Tuy nhiên, giải pháp này khai báo mảng cố định (10000 phần tử) thay vì dùng biến đếm hoặc cấp phát động, và gán giá trị khởi tạo là phần tử đầu tiên của mảng. Logic tìm min/max là giống nhau, đạt độ phức tạp O(n).

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

Bài học kinh nghiệm

• Bài toán chênh lệch lớn nhất tương đương với bài toán tìm hiệu giữa giá trị lớn nhất và nhỏ nhất trong mảng.
• Phương pháp hiệu quả nhất là duyệt qua mảng một lần để tìm min và max, thay vì sắp xếp.

Lỗi thường gặp

• Sử dụng thuật toán sắp xếp không hiệu quả (như Bubble Sort) dẫn đến TLE (Time Limit Exceeded) với dữ liệu lớn.
• Quên xử lý trường hợp mảng có thể chứa số âm hoặc số dương lớn khi khởi tạo giá trị min/max ban đầu.