מצא את הערך המרבי של ABS(I - J) * MIN(ARR[I], ARR[J]) במערך ARR[]

נתון מערך של n אלמנטים נפרדים. מצא את המקסימום של המכפלה של מינימום של שני מספרים במערך והפרש מוחלט של מיקומם, כלומר מצא את הערך המקסימלי של abs(i - j) * min(arr[i] arr[j]) כאשר i ו-j משתנים מ-0 ל-n-1.

דוגמאות:

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 מצא את הערך המקסימלי נסה את זה!

א פתרון פשוט שכן בעיה זו היא לקחת כל אלמנט אחד אחד ולהשוות אלמנט זה עם האלמנטים מימין לו. לאחר מכן חשב מכפלה של מינימום מהם והפרש מוחלט בין המדדים שלהם ומקסם את התוצאה. מורכבות הזמן עבור גישה זו היא O(n^2).

א פתרון יעיל כדי לפתור את הבעיה במורכבות זמן ליניארית. אנחנו לוקחים שני איטרטורים שמאל=0 ו ימין=n-1 השוו בין האלמנטים arr[Left] ו-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)

להלן יישום הרעיון לעיל.

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>

תְפוּקָה

מורכבות זמן: O(N log N) כאן N הוא אורך מערך.

מורכבות החלל: O(1) מכיוון שלא נעשה שימוש בשטח נוסף.

איך זה עובד?
הדבר החשוב להראות שאנחנו לא מפספסים אף זוג פוטנציאלי באלגוריתם הליניארי מעל, כלומר אנחנו צריכים להראות שביצוע שמאלה++ או ימינה-- לא מוביל למקרה שבו היינו מקבלים ערך גבוה יותר של maxProduct.

שימו לב שאנחנו תמיד מכפילים עם (ימין - שמאל).

אם מגיעים[שמאל] < arr[right] then smaller values of יָמִינָה עבור שמאל נוכחי הם חסרי תועלת מכיוון שהם לא יכולים לייצר ערך גבוה יותר של maxProduct (מכיוון שאנו מכפילים עם arr[שמאל] עם (ימין - שמאל)). מה אם arr[שמאל] היה גדול יותר מכל אחד מהאלמנטים בצד השמאלי שלו. במקרה זה חייב להימצא זוג טוב יותר עבור אותו אלמנט עם הזכות הנוכחית. לכן נוכל להגדיל בבטחה שמאלה מבלי לפספס שום זוג טוב יותר עם הזרם השמאלי.
טיעונים דומים ישימים כאשר arr[right] < arr[left].