大小为2的组之间的最大差异-yiteyi-C++库

给定一个偶数个元素的数组，使用这些数组元素形成2个组，这样总和最高的组和总和最低的组之间的差值最大。注：一个元素只能是一个组的一部分，并且必须是至少一个组的一部分。 例如：

null

Input : arr[] = {1, 4, 9, 6}Output : 10Groups formed will be (1, 4) and (6, 9), the difference between highest sum group(6, 9) i.e 15 and lowest sum group (1, 4)i.e 5 is 10.Input : arr[] = {6, 7, 1, 11}Output : 11Groups formed will be (1, 6) and (7, 11), the difference between highest sum group(7, 11) i.e 18 and lowest sum group (1, 6)i.e 7 is 11.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

简单方法： 我们可以通过做出所有可能的组合，并检查具有最高和最低和的组之间的每组组合差异来解决这个问题。总共会形成n*（n-1）/2个这样的小组（nC2）。时间复杂度：O（n^3），因为生成组和检查每个组需要O（n^2），所以需要n次迭代，因此总体上需要O（n^3）时间。 有效方法： 我们可以使用贪婪的方法。对整个数组进行排序，我们的结果是最后两个元素的和减去前两个元素的和。

C++

                         // CPP program to find minimum difference                       
                         // between groups of highest and lowest                       
                         // sums.                       
                         #include <bits/stdc++.h>                       
                         #define ll long long int                       
                         using                                     namespace                                     std;                       
           
                         ll CalculateMax(ll arr[],                                     int                                     n)                       
                         {                       
                                                 // Sorting the whole array.                       
                                                 sort(arr, arr + n);                       
                                   
                                                 int                                     min_sum = arr[0] + arr[1];                       
                                                 int                                     max_sum = arr[n-1] + arr[n-2];                       
           
                                                 return                                     abs                                     (max_sum - min_sum);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 ll arr[] = { 6, 7, 1, 11 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << CalculateMax(arr, n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum difference                       
                         // between groups of highest and lowest                       
                         // sums.                       
                         import                                     java.util.Arrays;                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                         static                                     int                                     CalculateMax(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Sorting the whole array.                       
                                                 Arrays.sort(arr);                       
                                   
                                                 int                                     min_sum = arr[                                     0                                     ] + arr[                                     1                                     ];                       
                                                 int                                     max_sum = arr[n-                                     1                                     ] + arr[n-                                     2                                     ];                       
           
                                                 return                                     (Math.abs(max_sum - min_sum));                       
                         }                       
           
                         // Driver code                       
                                   
                                                 public                                     static                                     void                                     main (String[] args) {                       
           
                                                 int                                     arr[] = {                                     6                                     ,                                     7                                     ,                                     1                                     ,                                     11                                     };                       
                                                 int                                     n = arr.length;                       
                                                 System.out.println (CalculateMax(arr, n));                       
                                                 }                       
                         }                       

Python3

                         # Python 3 program to find minimum difference                       
                         # between groups of highest and lowest                       
                         def                                     CalculateMax(arr, n):                       
           
                                                 # Sorting the whole array.                       
                                                 arr.sort()                       
                                                 min_sum                                     =                                     arr[                                     0                                     ]                                     +                                     arr[                                     1                                     ]                       
                                                 max_sum                                     =                                     arr[n                                     -                                     1                                     ]                                     +                                     arr[n                                     -                                     2                                     ]                       
                                                 return                                     abs                                     (max_sum                                     -                                     min_sum)                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     6                                     ,                                     7                                     ,                                     1                                     ,                                     11                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (CalculateMax(arr, n))                       
           
                         # This code is contributed                       
                         # by Shrikant13                       

C#

                         // C# program to find minimum difference                       
                         // between groups of highest and lowest                       
                         // sums.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG{                       
           
                         static                                     int                                     CalculateMax(                                     int                                     []arr,                                     int                                     n)                       
                         {                       
                                                 // Sorting the whole array.                       
                                                 Array.Sort(arr);                       
                                   
                                                 int                                     min_sum = arr[0] + arr[1];                       
                                                 int                                     max_sum = arr[n-1] + arr[n-2];                       
           
                                                 return                                     (Math.Abs(max_sum - min_sum));                       
                         }                       
           
                         // Driver code                       
                                   
                                                 static                                     public                                     void                                     Main (){                       
                                                 int                                     []arr = { 6, 7, 1, 11 };                       
                                                 int                                     n = arr.Length;                       
                                                 Console.WriteLine(CalculateMax(arr, n));                       
                                                 }                       
                         //This code is contributed by Sachin.                       
                         }                       

PHP

                         <?php                       
                         // PHP program to find minimum                       
                         // difference between groups of                       
                         // highest and lowest sums.                       
                         function                                     CalculateMax(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // Sorting the whole array.                       
                                                 sort(                                     $arr                                     );                       
                                   
                                                 $min_sum                                     =                                     $arr                                     [0] +                       
                                                 $arr                                     [1];                       
                                                 $max_sum                                     =                                     $arr                                     [                                     $n                                     - 1] +                       
                                                 $arr                                     [                                     $n                                     - 2];                       
           
                                                 return                                     abs                                     (                                     $max_sum                                     -                       
                                                 $min_sum                                     );                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (6, 7, 1, 11 );                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         echo                                     CalculateMax(                                     $arr                                     ,                                     $n                                     ),                                     ""                                     ;                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript program to                       
                                                 // find minimum difference                       
                                                 // between groups of highest and lowest                       
                                                 // sums.                       
                                   
                                                 function                                     CalculateMax(arr, n)                       
                                                 {                       
                                                 // Sorting the whole array.                       
                                                 arr.sort(                                     function                                     (a, b){                                     return                                     a - b});                       
           
                                                 let min_sum = arr[0] + arr[1];                       
                                                 let max_sum = arr[n-1] + arr[n-2];                       
           
                                                 return                                     (Math.abs(max_sum - min_sum));                       
                                                 }                       
                                   
                                                 let arr = [ 6, 7, 1, 11 ];                       
                                                 let n = arr.length;                       
                                                 document.write(CalculateMax(arr, n));                       
                                   
                         </script>                       

输出：

时间复杂性： O（n*logn） 进一步优化： 代替排序，我们可以在线性时间中找到最大值2和最小值2，并将时间复杂度降低到O（n）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章