ZNAJDŹ MAKSYMALNĄ WARTOŚĆ ABS(I - J) * MIN(ARR[I], ARR[J]) W TABLICY ARR[]

Biorąc pod uwagę tablicę n różnych elementów. Znajdź maksimum iloczynu Minimum dwóch liczb w tablicy i bezwzględnej różnicy ich pozycji, tj. znajdź maksymalną wartość abs(i - j) * min(arr[i] arr[j]), gdzie i oraz j różnią się od 0 do n-1.

Przykłady:

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 Znajdź wartość maksymalną Spróbuj!

A proste rozwiązanie ponieważ ten problem polega na wzięciu każdego elementu jeden po drugim i porównaniu tego elementu z elementami po jego prawej stronie. Następnie oblicz iloczyn ich minimum i bezwzględnej różnicy pomiędzy ich indeksami i zmaksymalizuj wynik. Złożoność czasowa dla tego podejścia wynosi O(n^2).

Jakiś wydajne rozwiązanie rozwiązuje problem w liniowej złożoności czasowej. Bierzemy dwa iteratory Lewy=0 I Prawo = n-1 porównaj elementy arr[lewy] i arr[prawy].

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)

Poniżej realizacja powyższego pomysłu.

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# 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>

Wyjście

Złożoność czasowa: O(N log N) tutaj N jest długością tablicy.

Złożoność przestrzenna: O(1) ponieważ nie wykorzystuje się dodatkowej przestrzeni.

Jak to działa?
Ważną rzeczą jest pokazanie, że nie pomijamy żadnej potencjalnej pary w powyższym algorytmie liniowym, tj. musimy pokazać, że zrobienie w lewo++ lub w prawo nie prowadzi do przypadku, w którym otrzymalibyśmy wyższą wartość maxProduct.

Pamiętaj, że zawsze mnożymy przez (prawo - lewo).

Jeśli arr[po lewej] < arr[right] then smaller values of Prawidłowy dla prądu lewego są bezużyteczne, ponieważ nie mogą wygenerować wyższej wartości maxProduct (ponieważ mnożymy przez arr[lewy] przez (prawy - lewy)). Co by było, gdyby arr[left] było większe niż którykolwiek z elementów po jego lewej stronie. W takim przypadku musiała zostać znaleziona lepsza para dla tego elementu z obecnym prawym. Dlatego możemy bezpiecznie zwiększać lewą stronę, nie tracąc przy tym żadnej lepszej pary z obecną lewą stroną.
Podobne argumenty mają zastosowanie, gdy arr[right] < arr[left].