Atrast maksimālo abs(i - j) * min(arr[i], arr[j]) vērtību masīvā arr[]
Dots n atšķirīgu elementu masīvs. Atrodiet maksimālo reizinājumu ar minimālo divu skaitļu skaitu masīvā un to pozīciju absolūto atšķirību, t.i., atrodiet maksimālo vērtību abs(i - j) * min(arr[i] arr[j]), kur i un j svārstās no 0 līdz n-1.
Piemēri:
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 Atrodiet maksimālo vērtību Izmēģiniet to! A vienkāršs risinājums šī problēma ir ņemt katru elementu pa vienam un salīdzināt šo elementu ar elementiem labajā pusē. Pēc tam aprēķiniet to minimuma un to indeksu absolūtās starpības reizinājumu un palieliniet rezultātu. Laika sarežģītība šai pieejai ir O(n^2).
An efektīvs risinājums atrisināt problēmu lineārā laika sarežģītībā. Mēs ņemam divus iteratorus Pa kreisi=0 un Pa labi=n-1 salīdziniet elementus arr [pa kreisi] un arr [pa labi].
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)
Zemāk ir iepriekš minētās idejas īstenošana.
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>
Izvade
16
Laika sarežģītība: O(N log N) šeit N ir masīva garums.
Telpas sarežģītība: O(1) jo nav izmantota papildu vieta.
Kā tas darbojas?
Svarīgi, lai parādītu, ka mēs nepalaižam garām nevienu potenciālo pāri iepriekš minētajā lineārajā algoritmā, t.i., mums ir jāparāda, ka, veicot darbības pa kreisi++ vai pa labi, neizraisīsim gadījumu, kad mēs iegūtu lielāku maxProduct vērtību.
Lūdzu, ņemiet vērā, ka mēs vienmēr reizinām ar (pa labi - pa kreisi).
- Ja arr [pa kreisi] < arr[right] then smaller values of pareizi pašreizējam kreisajam ir bezjēdzīgi, jo tie nevar radīt lielāku maxProduct vērtību (jo mēs reizinām ar arr[pa kreisi] ar (labais - kreisais)). Ko darīt, ja arr[left] ir lielāks par jebkuru no tā kreisajā pusē esošajiem elementiem. Tādā gadījumā šim elementam ir jāatrod labāks pāris ar pašreizējām tiesībām. Tāpēc mēs varam droši palielināt kreiso pusi, nepalaižot garām nevienu labāku pāri ar pašreizējo kreiso.
- Līdzīgi argumenti ir piemērojami, ja arr[right] < arr[left].
