logo

TechCodeview

Nájdite maximálnu hodnotu abs(i - j) * min(arr[i], arr[j]) v poli arr[]

Dané pole n rôznych prvkov. Nájdite maximum súčinu minima dvoch čísel v poli a absolútny rozdiel ich pozícií, t. j. nájdite maximálnu hodnotu abs(i - j) * min(arr[i] arr[j]), kde i a j sa menia od 0 do n-1. 

java regex pre

Príklady:  

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 Nájdite maximálnu hodnotu Skúste to!

A jednoduché riešenie pretože tento problém je vziať každý prvok jeden po druhom a porovnať tento prvok s prvkami napravo od neho. Potom vypočítajte súčin minima z nich a absolútneho rozdielu medzi ich indexmi a maximalizujte výsledok. Časová zložitosť pre tento prístup je O(n^2).



An efektívne riešenie riešiť problém v lineárnej časovej zložitosti. Vezmeme dva iterátory Vľavo = 0 a vpravo=n-1 porovnajte prvky arr[Left] a 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)

Nižšie je uvedená implementácia vyššie uvedenej myšlienky. 

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(arrn);  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(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# 
// 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>

Výstup 
16

Časová zložitosť: O(N log N) tu N je dĺžka poľa.

Priestorová zložitosť: O(1) pretože sa nepoužíva žiadny ďalší priestor.

Ako to funguje?  
Dôležité je ukázať, že nám vo vyššie uvedenom lineárnom algoritme nechýba žiadny potenciálny pár, t.j. musíme ukázať, že robenie vľavo ++ alebo vpravo nevedie k prípadu, kedy by sme dostali vyššiu hodnotu maxProduct.

Upozorňujeme, že vždy násobíme pomocou (vpravo - vľavo). 

  1. Ak arr[vľavo]< arr[right] then smaller values of správne pre prúd vľavo sú zbytočné, pretože nemôžu produkovať vyššiu hodnotu maxProduct (pretože násobíme s arr[left] s (right - left)). Čo ak arr[left] bol väčší ako ktorýkoľvek z prvkov na jeho ľavej strane. V takom prípade sa musí nájsť lepší pár pre tento prvok s aktuálnym právom. Preto môžeme bezpečne zvýšiť vľavo bez toho, aby sme vynechali lepší pár so ľavým prúdom.
  2. Podobné argumenty sú použiteľné, keď arr[vpravo]< arr[left].