Rechercher la valeur maximale de abs(i - j) * min(arr[i], arr[j]) dans un tableau arr[]
Étant donné un tableau de n éléments distincts. Trouvez le maximum du produit du minimum de deux nombres dans le tableau et la différence absolue de leurs positions, c'est-à-dire trouvez la valeur maximale de abs(i - j) * min(arr[i] arr[j]) où i et j varient de 0 à n-1.
Exemples :
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 Rechercher la valeur maximale Essayez-le ! UN solution simple car ce problème consiste à prendre chaque élément un par un et à comparer cet élément avec les éléments à sa droite. Calculez ensuite le produit du minimum d'entre eux et la différence absolue entre leurs indices et maximisez le résultat. La complexité temporelle de cette approche est O(n^2).
Un solution efficace pour résoudre le problème en complexité temporelle linéaire. On prend deux itérateurs Gauche=0 et Droite=n-1 comparer les éléments arr[Left] et 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)
Vous trouverez ci-dessous la mise en œuvre de l’idée ci-dessus.
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>
Sortir
16
Complexité temporelle : O(N log N) ici N est la longueur du tableau.
Complexité spatiale : O(1) puisqu'aucun espace supplémentaire n'est utilisé.
Comment cela marche-t-il?
La chose importante est de montrer que nous ne manquons aucune paire potentielle dans l'algorithme linéaire ci-dessus, c'est-à-dire que nous devons montrer que faire left++ ou right-- ne conduit pas à un cas où nous aurions obtenu une valeur plus élevée de maxProduct.
Veuillez noter que nous multiplions toujours par (droite - gauche).
- Si arr[gauche] < arr[right] then smaller values of droite pour la gauche actuelle sont inutiles car ils ne peuvent pas produire une valeur plus élevée de maxProduct (car nous multiplions avec arr[left] par (right - left)). Et si arr[left] était supérieur à n'importe lequel des éléments de son côté gauche. Dans ce cas, une meilleure paire pour cet élément doit avoir été trouvée avec le droit actuel. Par conséquent, nous pouvons augmenter en toute sécurité la gauche sans manquer une meilleure paire avec la gauche actuelle.
- Des arguments similaires sont applicables lorsque arr[right] < arr[left].
