Giá trị lớn nhất của |arr[i] – arr[j]| + |i – j| trong C++

Trong bài toán này, chúng ta được cho một mảng n số nguyên. Nhiệm vụ là tạo một chương trình tìm giá trị lớn nhất của |arr[i]-arr[j]| + |i-j|.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào – mảng = {4, 1, 2}

Đầu ra – 4

Giải thích –

|arr[0] - arr[1]|+|0-1| = |4-1| + |-1| = 3+1 = 4
|arr[0] - arr[2]|+|0-2| = |4-2| + |-2| = 2+2 = 4
|arr[1] - arr[2]|+|1-2| = |1-2| + |1-2| = 1+1 = 2

Để giải quyết bài toán này, một cách tiếp cận đơn giản sẽ là sử dụng cách brute force sử dụng hai vòng lặp và tìm hiệu lớn nhất.

Nhưng một cách tiếp cận hiệu quả sẽ sử dụng các tính chất của hàm tuyệt đối:

Hãy giải mã phương trình và tìm giải pháp:

arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i]-i) -(arr[j]-j)}
-arr[i] + arr[j] - i + j = -{(arr[i]+i) - (arr[j]+j)}

Thứ nhất và thứ tư giống nhau, thứ hai và thứ tư giống nhau. Sử dụng điều này, chúng ta sẽ tạo hai mảng lưu giá trị arr[i] +/- i.

mảng1 sẽ lưu giá trị arr[i] + i

mảng2 sẽ lưu giá trị arr[i] - i

Vì vậy, chúng ta sẽ tìm giá trị lớn nhất của hai giá trị:

max ((max(mảng1)-min(mảng1)), (max(mảng2)-min(mảng2)))

Ví dụ

Chương trình minh họa triển khai giải pháp của chúng ta,

#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
    return ans;
}
int main() {
    int array[] = { 5, 7, 1, 2 };
    int n = sizeof(array) / sizeof(array[0]);
    cout<<"Giá trị lớn nhất của |arr[i] - arr[j]| + |i-j| là "<<maxDiff(array, n);
    return 0;
}

Kết quả

Giá trị lớn nhất của |arr[i] - arr[j]| + |i-j| là 7