兩個大小的組之間的最大差異 · GeeksForGeeks 中文系列教程

# 兩個大小的組之間的最大差異 > 原文： [https://www.geeksforgeeks.org/maximum-difference-groups-size-two/](https://www.geeksforgeeks.org/maximum-difference-groups-size-two/) 給定一個偶數個元素的數組，請使用這些數組元素形成 2 個組，以使總和最高的組與總和最低的組之間的差最大。 **注意**：一個元素只能是一個組的一部分，并且必須是至少一個組的一部分。 **示例**： ``` Input : arr[] = {1, 4, 9, 6} Output : 10 Groups 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 : 11 Groups 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. ``` **簡單方法**：我們可以通過進行所有可能的組合并檢查最高和最低組之間的每組組合差異來解決此問題。總共將形成 n *（n-1）/ 2 個這樣的基團（nC2）。時間復雜度：O（n ^ 3），因為將花費 O（n ^ 2）來生成組并檢查每個組 n 次迭代，因此總體上需要 O（n ^ 3）時間。 **有效方法**：我們可以使用貪婪方法。對整個數組進行排序，我們的結果是最后兩個元素的總和減去前兩個元素的總和。 ## C++ ```cpp // 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 // 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 ```py # 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# ```cs // 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 // 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), "\n" ; // This code is contributed by ajit ?> ``` **輸出**： ``` 11 ``` **時間復雜度**： O（n * log n） **進一步優化**：除了排序，我們還可以在線性時間中找到最大 2 個和最小 2 個，并將時間復雜度降低到`O(n)`。 [](https://practice.geeksforgeeks.org/courses/competitive-programming-live?utm_source=geeksforgeeks&utm_medium=article&utm_campaign=gfg_article_cp) * * * * * *