Duotas n skirtingų elementų masyvas. Raskite maksimalų masyvo dviejų skaičių sandaugą ir absoliutų jų padėties skirtumą, t. y. raskite didžiausią abs(i - j) * min(arr[i] arr[j]) reikšmę, kur i ir j svyruoja nuo 0 iki n-1.
žemėlapis mašinraščiu
Pavyzdžiai:
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 Raskite maksimalią vertę Išbandykite! A paprastas sprendimas Ši problema yra paimti kiekvieną elementą po vieną ir palyginti šį elementą su elementais, esančiais dešinėje. Tada apskaičiuokite minimalaus jų ir absoliutaus skirtumo tarp jų indeksų sandaugą ir padidinkite rezultatą. Šio metodo laiko sudėtingumas yra O(n^2).
An efektyvus sprendimas išspręsti problemą tiesiniu laiko sudėtingumu. Imame du iteratorius Kairė = 0 ir Dešinė = n-1 palyginkite elementus arr [Left] ir 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)
Žemiau yra aukščiau pateiktos idėjos įgyvendinimas.
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>
Išvestis
16
Laiko sudėtingumas: O (N log N) čia N yra masyvo ilgis.
Erdvės sudėtingumas: O(1) nes nenaudojama papildomos vietos.
Kaip tai veikia?
Svarbu parodyti, kad nepraleidžiame jokios potencialios poros aukščiau esančiame linijiniame algoritme, t.
Atkreipkite dėmesį, kad mes visada dauginame su (dešinė - kairė).
- Jei arr [kairėn]< arr[right] then smaller values of teisingai srovės kairėje yra nenaudingos, nes jos negali sukurti didesnės maxProduct vertės (nes dauginame iš arr[left] su (dešinė - kairė)). Ką daryti, jei arr [left] yra didesnis nei bet kuris elementas kairėje pusėje. Tokiu atveju turi būti rasta geresnė šio elemento pora su dabartine teise. Todėl galime drąsiai padidinti kairę, nepraleisdami geresnės poros su srove.
- Panašūs argumentai taikomi, kai arr[right]< arr[left].