इस समस्या में, हमें n इंटीजर्स का एक ऐरे दिया गया है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो |arr[i]-arr[j]| + |i-j| का अधिकतम मान ढूंढे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट − array = {4, 1, 2}
आउटपुट − 4
व्याख्या −
|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
इस समस्या को हल करने के लिए, एक सरल दृष्टिकोण ब्रूट फोर्स दृष्टिकोण का उपयोग करना होगा जो दो लूप्स का उपयोग करेगा और अधिकतम अंतर ढूंढेगा।
लेकिन एक कुशल दृष्टिकोण निरपेक्ष फंक्शन के गुणों का उपयोग करना होगा,
आइए समीकरण को डिकोड करें और समाधान ढूंढें,
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)}पहला और चौथा समान हैं और दूसरा और चौथा समान हैं। इसका उपयोग करके हम दो ऐरे बनाएंगे जो arr[i]+- i मान संग्रहीत करेंगे।
array1 मान arr[i] + i संग्रहीत करेगा
array2 मान arr[i] - i संग्रहीत करेगा
तो, हम दो मानों में से अधिकतम ढूंढेंगे जो हैं
max ((max(array1)-min(array1)), (max(array2)-min(array2)))
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,
#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; }आउटपुट
The maximum value of |arr[i] - arr[j]| + |i-j| is 7
