Trong bài toán này, chúng ta được cung cấp một mảng gồm n số nguyên. Nhiệm vụ của chúng ta 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 lấy một ví dụ để hiểu vấ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 vấn đề này, một cách tiếp cận đơn giản sẽ là sử dụng bạo lực phương pháp tiếp cận sẽ sử dụng hai vòng lặp và tìm ra sự khác biệt tối đa.
Nhưng một cách tiếp cận hiệu quả sẽ sử dụng các thuộc tính của hàm tuyệt đối,
Hãy giải mã phương trình và tìm lời giải,
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)} Đầu tiên và đầu tiên là giống nhau và thứ hai và thứ tư là như nhau. Sử dụng điều này, chúng tôi sẽ tạo hai mảng sẽ lưu trữ các giá trị arr [i] + - i.
array1 sẽ lưu trữ các giá trị arr [i] + i
array2 sẽ lưu trữ các giá trị arr [i] - i
Vì vậy, chúng tôi sẽ tìm giá trị tối đa của hai giá trị là
max ((max (array1) -min (array1)), (max (array2) -min (array2)))
Ví dụ
Chương trình hiển thị việc triển khai giải pháp của chúng tôi,
#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<<"The maximum value of |arr[i] - arr[j]| + |i-j| is "<<maxDiff(array, n);
return 0;
} Đầu ra
The maximum value of |arr[i] - arr[j]| + |i-j| is 7