Chương trình tìm chênh lệch chỉ số lớn nhất giữa hai số khác nhau trong C++

Cho mảng arr[] n số nguyên. Tìm chênh lệch chỉ số lớn nhất giữa hai phần tử khác nhau.

Mô tả bài toán

Tìm max(|i-j|) với arr[i] != arr[j].

Ví dụ

Đầu vào: arr[] = {4, 1, 3, 2, 1, 2, 4}

Đầu ra: 5

Giải thích: Chênh lệch giữa chỉ số 0 (giá trị 4) và chỉ số 5 (giá trị 2).

Phương pháp giải

Chỉ cần so sánh phần tử đầu với các phần tử khác từ hai đầu:

• Tìm chỉ số xa nhất từ đầu có giá trị khác arr[0] (duyệt từ cuối về)
• Tìm chỉ số xa nhất từ cuối có giá trị khác arr[0] (duyệt từ đầu về)
• Kết quả là max của hai giá trị trên

Chương trình minh họa

#include <iostream> 
using namespace std; 

int maximum(int a, int b) { 
    return (a > b) ? a : b; 
} 

int CalcMaxIndDiff(int a[], int n) { 
    int indDiff1 = 0, indDiff2 = 0; 
    int i = 0; 
    while(i < (n - 1)) { 
        if(a[0] != a[i]) { indDiff2 = i; break; } 
        i++; 
    } 
    i = (n - 1); 
    while(i > 0) { 
        if(a[0] != a[i]) { indDiff1 = i; break; } 
        i--; 
    } 
    return maximum(indDiff1, indDiff2); 
} 

int main() { 
    int arr[] = {4, 1, 3, 2, 1, 2, 4}; 
    int n = 7; 
    cout << "The maximum difference between the index of any two different numbers is " << CalcMaxIndDiff(arr, n); 
    return 0; 
}

Đầu ra: The maximum difference between the index of any two different numbers is 5