Etsi abs(i - j) * min(arr[i], arr[j]) enimmäisarvo taulukosta arr[]
Annettu joukko n erillistä elementtiä. Etsi taulukon kahden luvun minimitulo ja niiden sijaintien absoluuttinen ero eli löydä abs(i - j) * min(arr[i] arr[j]) maksimiarvo, jossa i ja j vaihtelevat välillä 0 - n-1.
Esimerkkejä:
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 Etsi enimmäisarvo Kokeile sitä! A yksinkertainen ratkaisu Tämä ongelma on ottaa jokainen elementti yksitellen ja verrata tätä elementtiä sen oikealla puolella oleviin elementteihin. Laske sitten niiden minimin ja niiden indeksien absoluuttisen eron tulo ja maksimoi tulos. Tämän lähestymistavan aikamonimutkaisuus on O(n^2).
An tehokas ratkaisu ratkaisemaan ongelman lineaarisessa ajassa. Otamme kaksi iteraattoria Vasen = 0 ja Oikea = n-1 vertaa elementtejä arr[vasen] ja arr[oikea].
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)
Alla yllä olevan idean toteutus.
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>
Lähtö
16
Aika monimutkaisuus: O(N log N) tässä N on taulukon pituus.
Tilan monimutkaisuus: O(1) koska ylimääräistä tilaa ei ole käytetty.
Miten tämä toimii?
Tärkeintä on osoittaa, että emme missaa yhtäkään mahdollista paria yllä olevassa lineaarisessa algoritmissa, eli meidän on osoitettava, että vasen++ tai oikea-- ei johda tapaukseen, jossa olisimme saaneet korkeamman maxProduct-arvon.
Huomaa, että kerromme aina arvolla (oikea - vasen).
- Jos arr[vasen] < arr[right] then smaller values of oikein nykyiselle vasemmalle ovat hyödyttömiä, koska ne eivät voi tuottaa suurempaa arvoa maxProduct (koska kerromme kanssa arr[vasen] ja (oikea - vasen)). Entä jos arr[vasen] on suurempi kuin mikään sen vasemmalla puolella olevista elementeistä. Siinä tapauksessa tälle elementille on täytynyt löytää parempi pari nykyisellä oikealla. Siksi voimme turvallisesti kasvattaa vasenta puuttumatta yhtään parempaa paria jäljellä olevan virran kanssa.
- Samanlaisia argumentteja voidaan käyttää, kun arr[oikea] < arr[left].
