इस समस्या में, हमें N पूर्णांक मानों वाली एक सरणी arr[] दी गई है। हमारा कार्य सरणी arr[] में abs(i – j) * min(arr[i], arr[j]) का अधिकतम मान ज्ञात करना है।
समस्या विवरण - हमें दो तत्वों के न्यूनतम मान और उनके इंडेक्स के बीच निरपेक्ष अंतर के गुणनफल का अधिकतम मान खोजना है। यानी दो मान i और j के लिए, हमें अधिकतम करना है: abs(i - j) * min(arr[i], arr[j])।
इनपुट
arr[] = {5, 7, 3, 6, 4}आउटपुट
16
व्याख्या
अधिकतम मान 16 है, इंडेक्स 0 और 4 के बीच => abs(0 - 4)*min(arr[0], arr[4]) => 4*min(5, 4) => 4*4 = 16
समाधान दृष्टिकोण
समस्या का एक सरल समाधान नेस्टेड लूप का उपयोग करना है। हम दो लूप लेंगे और i और j के प्रत्येक जोड़े के लिए मान की गणना करेंगे। और फिर पाए गए सभी मानों में से अधिकतम लौटाएँगे।
यह दृष्टिकोण अच्छा है लेकिन इसकी समय जटिलता O(n²) क्रम की है।
समस्या का एक प्रभावी समाधान दो इटरेटर मानों का उपयोग करना है, एक सरणी की शुरुआत से और दूसरा अंत से। इटरेटर्स के प्रत्येक मान के लिए हम आवश्यक मान खोजेंगे और उनकी तुलना करेंगे और अधिकतम को maxVal चर में संग्रहीत करेंगे। हम इसे तब तक करेंगे जब तक दोनों इटरेटर्स एक-दूसरे को पार न कर लें और अंत में maxVal लौटाएँगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
उदाहरण
#include<iostream> using namespace std; int calcMaxProdValue(int arr[], int n) { int maxVal = -100; int currentVal; int start = 0, end = n-1; while (start < end) { if (arr[start] < arr[end]) { currentVal = arr[start]*(end-start); start++; } else { currentVal = arr[end]*(end-start); end--; } maxVal = max(maxVal, currentVal); } return maxVal; } int main(){ int arr[] = {5, 7, 3, 6, 4}; int n = sizeof(arr)/sizeof(arr[0]); cout<<"The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is "<<calcMaxProdValue(arr,n); return 0; }आउटपुट
The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is 16
