एब्स (i - j) * min(arr[i], arr[j]) का अधिकतम मान C++ में arr [] में खोजें

इस समस्या में, हमें एन पूर्णांक मानों पर जोर देते हुए एक सरणी गिरफ्तारी [] दी जाती है। हमारा कार्य एक सरणी [] में एब्स (i - j) * मिनट (arr [i], arr [j]) का अधिकतम मान ज्ञात करना है।

समस्या का विवरण - हमें दो तत्वों के न्यूनतम मूल्य का अधिकतम उत्पाद मूल्य और उनके सूचकांक के बीच पूर्ण अंतर खोजने की आवश्यकता है। यानी दो मानों i और j के लिए, हमें अधिकतम करने की आवश्यकता है, abs(i - j) * min(arr[i] , arr[j])।

इनपुट

arr[] = {5, 7, 3, 6, 4}

आउटपुट

16

स्पष्टीकरण

The maximum value is 16, between index 0 and 4
=> abs(0 - 4)*min(arr[0], arr[4])
=> 4*min(5, 4) => 4*4 = 16

समाधान दृष्टिकोण

समस्या का एक आसान समाधान नेस्टेड लूप का उपयोग कर रहा है। हम दो लूप लेंगे और i और j के प्रत्येक जोड़े के लिए मान की गणना करेंगे। और फिर पाए गए सभी मानों में से अधिकतम लौटाएं।

यह दृष्टिकोण अच्छा है, लेकिन O(n ² .) के क्रम का समय जटिल है )।

समस्या का एक प्रभावी समाधान सरणी के अंत से दूसरे की शुरुआत से दो पुनरावर्तक मानों का उपयोग कर रहा है। इटरेटर के प्रत्येक मान के लिए हम आवश्यक मान ढूंढेंगे और उनकी तुलना करेंगे और अधिकतम inmaxVal वैरिएबल को स्टोर करेंगे। हम ऐसा तब तक करेंगे जब तक कि दोनों इटरेटर एक-दूसरे को पार नहीं कर लेते और अंत में मैक्सवेल वापस नहीं कर देते।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#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