โปรแกรมหาความต่างสูงสุดของดัชนีระหว่างตัวเลขที่ต่างกันใน C++

คำอธิบายโจทย์

อาร์เรย์ arr[] หาความต่างดัชนีสูงสุด |i-j| ที่ arr[i] != arr[j]

ตัวอย่าง

arr = {4, 1, 3, 2, 1, 2, 4} → Output: 5

index 0 (ค่า 4) และ index 5 (ค่า 2) ต่างกัน → diff = 5

วิธีแก้ปัญหา

เปรียบเทียบค่าแรก (arr[0]) กับค่าอื่นๆ หาดัชนีไกลสุดที่ต่างจาก arr[0]:

• สแกนซ้าย→ขวา หา index แรกที่ != arr[0] → indDiff2
• สแกนขวา→ซ้าย หา index สุดท้ายที่ != arr[0] → indDiff1
• คำตอบ = max(indDiff1, indDiff2)

เหตุผล: คู่ที่ห่างมากที่สุดต้องมีตัวหนึ่งเป็นปลายอาร์เรย์

โค้ดตัวอย่าง

#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, 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 << "Max index diff: " << CalcMaxIndDiff(arr, n);
    return 0;
}

ผลลัพธ์

Max index diff: 5