נתון מערך של 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 ו ימין=n-1 השוו בין האלמנטים arr[Left] ו-arr[right].
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
// 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.
# Python implementation of code # Function to calculate # maximum value of # abs(i - j) * min(arr[i] # arr[j]) in arr[] def Maximum_Product(arrn): # 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(arrn)) # This code is contributed # by Anant Agarwal.
// 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 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. ?> <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[שמאל] עם (ימין - שמאל)). מה אם arr[שמאל] היה גדול יותר מכל אחד מהאלמנטים בצד השמאלי שלו. במקרה זה חייב להימצא זוג טוב יותר עבור אותו אלמנט עם הזכות הנוכחית. לכן נוכל להגדיל בבטחה שמאלה מבלי לפספס שום זוג טוב יותר עם הזרם השמאלי.
- טיעונים דומים ישימים כאשר arr[right]< arr[left].