ابحث عن القيمة القصوى لـ abs(i - j) * min(arr[i], arr[j]) في صفيف arr[]
نظرا لمجموعة من العناصر المميزة n. ابحث عن الحد الأقصى لمنتج الحد الأدنى من رقمين في المصفوفة والفرق المطلق لمواضعهما، أي ابحث عن القيمة القصوى لـ abs(i - j) * min(arr[i] arr[j]) حيث يختلف i وj من 0 إلى n-1.
أمثلة :
Input : arr[] = {3 2 1 4} Output: 9 // arr[0] = 3 and arr[3] = 4 minimum of them is 3 and // absolute difference between their position is // abs(0-3) = 3. So product is 3*3 = 9 Input : arr[] = {8 1 9 4} Output: 16 // arr[0] = 8 and arr[2] = 9 minimum of them is 8 and // absolute difference between their position is // abs(0-2) = 2. So product is 8*2 = 16 Recommended Practice العثور على القيمة القصوى جربه! أ حل بسيط لأن هذه المشكلة هي أن تأخذ كل عنصر واحدًا تلو الآخر وتقارن هذا العنصر بالعناصر التي على يمينه. ثم قم بحساب منتج الحد الأدنى منها والفرق المطلق بين فهارسها وتعظيم النتيجة. التعقيد الزمني لهذا النهج هو O(n^2).
ان حل فعال لحل المشكلة في تعقيد الوقت الخطي. نحن نأخذ اثنين من التكرارات اليسار = 0 و اليمين=ن-1 قارن بين العنصرين arr[يسار] وarr[يمين].
left = 0 right = n-1 maxProduct = -INF While (left < right) If arr[Left] < arr[right] currProduct = arr[Left]*(right-Left) Left++ . If arr[right] < arr[Left] currProduct = arr[Right]*(Right-Left) Right-- . maxProduct = max(maxProduct currProduct)
وفيما يلي تنفيذ الفكرة المذكورة أعلاه.
C++ // C++ implementation of code #include using namespace std ; // Function to calculate maximum value of // abs(i - j) * min(arr[i] arr[j]) in arr[] int Maximum_Product ( int arr [] int n ) { int maxProduct = INT_MIN ; // Initialize result int currProduct ; // product of current pair // loop until they meet with each other int Left = 0 right = n -1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ]) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } else // arr[right] is smaller { currProduct = arr [ right ] * ( right - Left ); right -- ; } // maximizing the product maxProduct = max ( maxProduct currProduct ); } return maxProduct ; } // Driver program to test the case int main () { int arr [] = { 8 1 9 4 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < Maximum_Product ( arr n ); return 0 ; }
Java // Java implementation of code import java.util.* ; class GFG { // Function to calculate maximum value of // abs(i - j) * min(arr[i] arr[j]) in arr[] static int Maximum_Product ( int arr [] int n ) { // Initialize result int maxProduct = Integer . MIN_VALUE ; // product of current pair int currProduct ; // loop until they meet with each other int Left = 0 right = n - 1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ] ) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } // arr[right] is smaller else { currProduct = arr [ right ] * ( right - Left ); right -- ; } // maximizing the product maxProduct = Math . max ( maxProduct currProduct ); } return maxProduct ; } // Driver code public static void main ( String [] args ) { int arr [] = { 8 1 9 4 }; int n = arr . length ; System . out . print ( Maximum_Product ( arr n )); } } // This code is contributed by Anant Agarwal.
Python3 # Python implementation of code # Function to calculate # maximum value of # abs(i - j) * min(arr[i] # arr[j]) in arr[] def Maximum_Product ( arr n ): # Initialize result maxProduct = - 2147483648 # product of current pair currProduct = 0 # loop until they meet with each other Left = 0 right = n - 1 while ( Left < right ): if ( arr [ Left ] < arr [ right ]): currProduct = arr [ Left ] * ( right - Left ) Left += 1 else : # arr[right] is smaller currProduct = arr [ right ] * ( right - Left ) right -= 1 # maximizing the product maxProduct = max ( maxProduct currProduct ) return maxProduct # Driver code arr = [ 8 1 9 4 ] n = len ( arr ) print ( Maximum_Product ( arr n )) # This code is contributed # by Anant Agarwal.
C# // C# implementation of code using System ; class GFG { // Function to calculate maximum // value of abs(i - j) * min(arr[i] // arr[j]) in arr[] static int Maximum_Product ( int [] arr int n ) { // Initialize result int maxProduct = int . MinValue ; // product of current pair int currProduct ; // loop until they meet // with each other int Left = 0 right = n - 1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ]) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } // arr[right] is smaller else { currProduct = arr [ right ] * ( right - Left ); right -- ; } // maximizing the product maxProduct = Math . Max ( maxProduct currProduct ); } return maxProduct ; } // Driver code public static void Main () { int [] arr = { 8 1 9 4 }; int n = arr . Length ; Console . Write ( Maximum_Product ( arr n )); } } // This code is contributed by nitin mittal.
PHP // PHP implementation of code // Function to calculate // maximum value of // abs(i - j) * min(arr[i] // arr[j]) in arr[] function Maximum_Product ( $arr $n ) { $INT_MIN = 0 ; // Initialize result $maxProduct = $INT_MIN ; // product of current pair $currProduct ; // loop until they meet // with each other $Left = 0 ; $right = $n - 1 ; while ( $Left < $right ) { if ( $arr [ $Left ] < $arr [ $right ]) { $currProduct = $arr [ $Left ] * ( $right - $Left ); $Left ++ ; } // arr[right] is smaller else { $currProduct = $arr [ $right ] * ( $right - $Left ); $right -- ; } // maximizing the product $maxProduct = max ( $maxProduct $currProduct ); } return $maxProduct ; } // Driver Code $arr = array ( 8 1 9 4 ); $n = sizeof ( $arr ) / sizeof ( $arr [ 0 ]); echo Maximum_Product ( $arr $n ); // This code is contributed // by nitin mittal. ?>
JavaScript < script > // Javascript implementation of code // Function to calculate // maximum value of // abs(i - j) * min(arr[i] // arr[j]) in arr[] function Maximum_Product ( arr n ) { let INT_MIN = 0 ; // Initialize result let maxProduct = INT_MIN ; // Product of current pair let currProduct ; // Loop until they meet // with each other let Left = 0 right = n - 1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ]) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } // arr[right] is smaller else { currProduct = arr [ right ] * ( right - Left ); right -- ; } // Maximizing the product maxProduct = Math . max ( maxProduct currProduct ); } return maxProduct ; } // Driver Code let arr = new Array ( 8 1 9 4 ); let n = arr . length ; document . write ( Maximum_Product ( arr n )); // This code is contributed by Saurabh Jaiswal < /script>
الإخراج
16
تعقيد الوقت : O(N log N) هنا N هو طول المصفوفة.
تعقيد الفضاء : O(1) نظرًا لعدم استخدام مساحة إضافية.
كيف يعمل هذا؟
الشيء المهم هو إظهار أننا لا نفتقد أي زوج محتمل في الخوارزمية الخطية أعلاه، أي أننا بحاجة إلى إظهار أن القيام باليسار ++ أو اليمين - لا يؤدي إلى حالة نحصل فيها على قيمة أعلى لـ maxProduct.
يرجى ملاحظة أننا نضرب دائمًا بـ (اليمين - اليسار).
- إذا وصل [يسار] < arr[right] then smaller values of يمين لليسار الحالي عديمة الفائدة لأنها لا تستطيع إنتاج قيمة أعلى لـ maxProduct (لأننا نضرب بـ arr[left] مع (right - left)). ماذا لو كان arr[left] أكبر من أي عنصر على جانبه الأيسر. في هذه الحالة، يجب العثور على زوج أفضل لهذا العنصر مع اليمين الحالي. لذلك يمكننا زيادة اليسار بأمان دون فقدان أي زوج أفضل مع اليسار الحالي.
- تنطبق الحجج المماثلة عندما arr[right] < arr[left].
