Hiệu tối đa giữa 2 phần tử với phần tử lớn hơn xuất hiện sau trong C

Cho mảng số nguyên. Tìm hiệu lớn nhất Arr[j] - Arr[i] sao cho j > i (phần tử lớn hơn xuất hiện sau phần tử nhỏ hơn).

Ví dụ

Đầu vào

Arr[] = { 2, 1, 3, 8, 3, 19, 21 }

Đầu ra - Hiệu tối đa: 20

Giải thích - Hiệu lớn nhất giữa 21 (chỉ số 6) và 1 (chỉ số 1), 21 xuất hiện sau 1.

Đầu vào

Arr[] = { 18, 2, 8, 1, 2, 3, 2, 6 }

Đầu ra - Hiệu tối đa: 6

Giải thích - Hiệu giữa 8 (chỉ số 2) và 2 (chỉ số 1).

Phương pháp tối ưu O(n)

• Theo dõi phần tử nhỏ nhất đã gặp (min_so_far)
• Với mỗi phần tử arr[i], tính hiệu = arr[i] - min_so_far
• Cập nhật maxDiff nếu hiệu lớn hơn
• Cập nhật min_so_far nếu arr[i] nhỏ hơn

Chương trình mẫu

#include <stdio.h>

int maxDiff(int arr[], int n) {
    int maxDiff = arr[1] - arr[0];
    int minVal = arr[0];
    
    for (int i = 1; i < n; i++) {
        if (arr[i] - minVal > maxDiff)
            maxDiff = arr[i] - minVal;
        if (arr[i] < minVal)
            minVal = arr[i];
    }
    return maxDiff;
}

int main() {
    int arr[] = {2, 5, 7, 3, 4, 12};
    int n = 6;
    printf("Hiệu tối đa (lớn hơn sau nhỏ hơn): %d", maxDiff(arr, n));
    return 0;
}

Kết quả

Hiệu tối đa (lớn hơn sau nhỏ hơn): 10

Giải thích: 12 - 2 = 10