# 最大化圓形數組中的連續差之和 > 原文： [https://www.geeksforgeeks.org/maximize-sum-consecutive-differences-circular-array/](https://www.geeksforgeeks.org/maximize-sum-consecutive-differences-circular-array/) 給定`n`個元素的數組。 將數組視為圓形數組，即`a[1]`為`a[n]`之后的元素。 任務是找到允許重排數組元素的連續元素之間的差的最大和，即在元素查找重排之后`|a[1] - a[2]| + |a[2] - a[3]| + ... + |a[n-1] - a[n]| + |a[n] - a[1]|`。 例子： ``` Input : arr[] = { 4, 2, 1, 8 } Output : 18 Rearrange given array as : { 1, 8, 2, 4 } Sum of difference between consecutive element = |1 - 8| + |8 - 2| + |2 - 4| + |4 - 1| = 7 + 6 + 2 + 3 = 18. Input : arr[] = { 10, 12, 15 } Output : 10 ``` 這個想法是使用貪婪方法，并嘗試將具有更大差異的元素拉近。 考慮給定數組的排序排列`a[1], a[1], a[2], ..., a[n-1], a[n]`使得`a[1] < a[2] < a[3] < ... < a[n-1] < a[n]`。 現在，要獲得在連續元素之間具有最大差異之和的答案，請按以下方式排列元素： `a[1], a[n], a[2], a[n-1], ..., a[n/2], a[n/2+1]` 該安排產生了最佳答案，因為所有`a[1], a[2], ..., a[n/2-1], a[n/2]`減去兩次，而`a[n/2+1], ..., a[n]`被添加兩次。 注`a[n/2+1]`僅對偶數`n`考慮此項，因為對于奇數`n`，它被加一次并相減一次，因此被抵消。 ## C++ ```cpp // C++ program to maximize the sum of difference // between consecutive elements in circular array #include <bits/stdc++.h> using namespace std; // Return the maximum Sum of difference between // consecutive elements. int maxSum(int arr[], int n) { ????int sum = 0; ????// Sorting the array. ????sort(arr, arr + n); ????// Subtracting a1, a2, a3,....., a(n/2)-1, an/2 ????// twice and adding a(n/2)+1, a(n/2)+2, a(n/2)+3,. ????// ...., an - 1, an twice. ????for (int i = 0; i < n/2; i++) ????{ ????????sum -= (2 * arr[i]); ????????sum += (2 * arr[n - i - 1]); ????} ????return sum; } // Driver Program int main() { ????int arr[] = { 4, 2, 1, 8 }; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << maxSum(arr, n) << endl; ????return 0; } ```