# 值和索引和的最大絕對差 > 原文： [https://www.geeksforgeeks.org/maximum-absolute-difference-value-index-sums/](https://www.geeksforgeeks.org/maximum-absolute-difference-value-index-sums/) 給定 N 個整數的未排序數組 A，對于所有 ***1*** ≤返回 *** f（i，j）*** 的最大值 *** i，j *** ≤ *** N. *** ***f（i，j）*** 或數組 A 的兩個元素的絕對差定義為 **| A [i] – A [j] | + | i – j |** ，其中 **| *A* |** 表示 *A* 的絕對值。 **示例**： ``` We will calculate the value of f(i, j) for each pair of (i, j) and return the maximum value thus obtained. Input : A = {1, 3, -1} Output : 5 f(1, 1) = f(2, 2) = f(3, 3) = 0 f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3 f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4 f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5 So, we return 5. Input : A = {3, -2, 5, -4} Output : 10 f(1, 1) = f(2, 2) = f(3, 3) = f(4, 4) = 0 f(1, 2) = f(2, 1) = |3 - (-2)| + |1 - 2| = 6 f(1, 3) = f(3, 1) = |3 - 5| + |1 - 3| = 4 f(1, 4) = f(4, 1) = |3 - (-4)| + |1 - 4| = 10 f(2, 3) = f(3, 2) = |(-2) - 5| + |2 - 3| = 8 f(2, 4) = f(4, 2) = |(-2) - (-4)| + |2 - 4| = 4 f(3, 4) = f(4, 3) = |5 - (-4)| + |3 - 4| = 10 So, we return 10 ``` **樸素暴力**方法是通過對所有此類對（i，j）進行迭代并計算最大絕對差來計算值 f（i，j），這將在下面實現。 ## C++ ```cpp // Brute force C++ program to calculate the // maximum absolute difference of an array. #include <bits/stdc++.h> using namespace std; int calculateDiff(int i, int j, int arr[]) { ????// Utility function to calculate ????// the value of absolute difference ????// for the pair (i, j). ????return abs(arr[i] - arr[j]) + abs(i - j); } // Function to return maximum absolute // difference in brute force. int maxDistance(int arr[], int n) { ????// Variable for storing the maximum ????// absolute distance throughout the ????// traversal of loops. ????int result = 0; ????// Iterate through all pairs. ????for (int i = 0; i < n; i++) { ????????for (int j = i; j < n; j++) { ????????????// If the absolute difference of ????????????// current pair (i, j) is greater ????????????// than the maximum difference ????????????// calculated till now, update ????????????// the value of result. ????????????if (calculateDiff(i, j, arr) > result) ????????????????result = calculateDiff(i, j, arr); ????????} ????} ????return result; } // Driver program to test the above function. int main() { ????int arr[] = { -70, -64, -6, -56, 64, ??????????????????61, -57, 16, 48, -98 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << maxDistance(arr, n) << endl; ????return 0; } ``` ## Java ```java // Java program to calculate the maximum // absolute difference of an array. public class MaximumAbsoluteDifference { ????private static int calculateDiff(int i, int j,? ?????????????????????????????????????int[] array) ????{ ????????// Utility function to calculate ????????// the value of absolute difference ????????// for the pair (i, j). ????????return Math.abs(array[i] - array[j]) +? ????????????????????????????Math.abs(i - j); ????} ????// Function to return maximum absolute ????// difference in brute force. ????private static int maxDistance(int[] array) ????{ ????????// Variable for storing the maximum ????????// absolute distance throughout the ????????// traversal of loops. ????????int result = 0; ????????// Iterate through all pairs. ????????for (int i = 0; i < array.length; i++)? ????????{ ????????????for (int j = i; j < array.length; j++) ????????????{ ????????????????// If the absolute difference of ????????????????// current pair (i, j) is greater ????????????????// than the maximum difference ????????????????// calculated till now, update ????????????????// the value of result. ????????????????result = Math.max(result, calculateDiff(i, j, array)); ????????????} ????????} ????????return result; ????} ????// Driver program to test above function ????public static void main(String[] args) ????{ ????????int[] array = { -70, -64, -6, -56, 64, ????????????????????????61, -57, 16, 48, -98 }; ????????System.out.println(maxDistance(array)); ????} } // This code is contributed by Harikrishnan Rajan ``` ## Python3 ```py # Brute force Python 3 program # to calculate the maximum? # absolute difference of an array. def calculateDiff(i, j, arr): ????# Utility function to calculate ????# the value of absolute difference ????# for the pair (i, j). ????return abs(arr[i] - arr[j]) + abs(i - j) # Function to return maximum? # absolute difference in? # brute force. def maxDistance(arr, n): ????# Variable for storing the ????# maximum absolute distance ????# throughout the traversal ????# of loops. ????result = 0 ????# Iterate through all pairs. ????for i in range(0,n): ????????for j in range(i, n): ????????????# If the absolute difference of ????????????# current pair (i, j) is greater ????????????# than the maximum difference ????????????# calculated till now, update ????????????# the value of result. ????????????if (calculateDiff(i, j, arr) > result): ????????????????result = calculateDiff(i, j, arr) ????return result # Driver program? arr = [ -70, -64, -6, -56, 64, ?????????61, -57, 16, 48, -98 ] n = len(arr) print(maxDistance(arr, n)) # This code is contributed by Smitha Dinesh Semwal ``` ## C# ```cs // C# program to calculate the maximum // absolute difference of an array. using System; public class MaximumAbsoluteDifference { ????private static int calculateDiff(int i, int j,? ????????????????????????????????????int[] array) ????{ ????????// Utility function to calculate ????????// the value of absolute difference ????????// for the pair (i, j). ????????return Math.Abs(array[i] - array[j]) +? ????????????????????????????Math.Abs(i - j); ????} ????// Function to return maximum absolute ????// difference in brute force. ????private static int maxDistance(int[] array) ????{ ????????// Variable for storing the maximum ????????// absolute distance throughout the ????????// traversal of loops. ????????int result = 0; ????????// Iterate through all pairs. ????????for (int i = 0; i < array.Length; i++)? ????????{ ????????????for (int j = i; j < array.Length; j++) ????????????{ ????????????????// If the absolute difference of ????????????????// current pair (i, j) is greater ????????????????// than the maximum difference ????????????????// calculated till now, update ????????????????// the value of result. ????????????????result = Math.Max(result, calculateDiff(i, j, array)); ????????????} ????????} ????????return result; ????} ????// Driver program ????public static void Main() ????{ ????????int[] array = { -70, -64, -6, -56, 64, ????????????????????????61, -57, 16, 48, -98 }; ????????Console.WriteLine(maxDistance(array)); ????} } // This code is contributed by vt_m ``` ## PHP ```php <?php // Brute force PHP program to? // calculate the maximum absolute? // difference of an array. function calculateDiff($i, $j, $arr) { ????// Utility function to calculate ????// the value of absolute difference ????// for the pair (i, j). ????return abs($arr[$i] - $arr[$j]) +? ???????????abs($i - $j); } // Function to return maximum // absolute difference in brute force. function maxDistance($arr, $n) { ????// Variable for storing the maximum ????// absolute distance throughout the ????// traversal of loops. ????$result = 0; ????// Iterate through all pairs. ????for ($i = 0; $i < $n; $i++)? ????{ ????????for ($j = $i; $j < $n; $j++)? ????????{ ????????????// If the absolute difference of ????????????// current pair (i, j) is greater ????????????// than the maximum difference ????????????// calculated till now, update ????????????// the value of result. ????????????if (calculateDiff($i, $j, $arr) > $result) ????????????????$result = calculateDiff($i, $j, $arr); ????????} ????} ????return $result; } // Driver Code $arr = array( -70, -64, -6, -56, 64, ???????????????61, -57, 16, 48, -98 ); $n = sizeof($arr); echo maxDistance($arr, $n); // This Code is contributed by mits? ?> ``` **輸出**： ``` 167 ``` **時間復雜度**： O（n ^ 2） 可以使用絕對值的屬性來計算`O(n)`時間復雜度的**高效**解決方案。 f（i，j）= | A [i] – A [j] | + | i – j | 可以用 4 種方式來寫（因為我們正在查看最大值，所以只要我們也以某種方式覆蓋最大值，我們甚至都不關心該值是否變為負值）。 ``` Case 1: A[i] > A[j] and i > j |A[i] - A[j]| = A[i] - A[j] |i -j| = i - j hence, f(i, j) = (A[i] + i) - (A[j] + j) Case 2: A[i] < A[j] and i < j |A[i] - A[j]| = -(A[i]) + A[j] |i -j| = -(i) + j hence, f(i, j) = -(A[i] + i) + (A[j] + j) Case 3: A[i] > A[j] and i < j |A[i] - A[j]| = A[i] - A[j] |i -j| = -(i) + j hence, f(i, j) = (A[i] - i) - (A[j] - j) Case 4: A[i] < A[j] and i > j |A[i] - A[j]| = -(A[i]) + A[j] |i -j| = i - j hence, f(i, j) = -(A[i] - i) + (A[j] - j) ``` 請注意，情況 1 和 2 是等效的，情況 3 和 4 也是等效的，因此我們只能針對兩種情況設計算法，因為它將涵蓋所有可能的情況。 > 1.在遍歷數組時，為數組的每個元素計算 A [i] + i 和 A [i] – i 的值。 > > 2.然后，對于兩個等效情況，我們找到最大可能值。 為此，我們必須為所有 i 存儲表達式 A [i] + i 和 A [i] – i 的最小值和最大值。 > > 3.因此，所需的最大絕對差為兩個值的最大值，即 max（（A [i] + i）–（A [j] + j））和 max（（A [i] – i）–（A [j ] – j））。 這些值可以在線性時間內輕松找到。 > a。 對于 max（（A [i] + i）–（A [j] + j）），維持兩個變量 max1 和 min1，它們將分別存儲 A [i] + i 的最大值和最小值。 max（（A [i] + i）–（A [j] + j））= max1 – min1 > b。 對于 max（（A [i] – i）–（A [j] – j））。 保持兩個變量 max2 和 min2，它們將分別存儲 A [i] – i 的最大值和最小值。 max（（A [i] – i）–（A [j] – j））= max2 – min2 下面給出使用上述快速算法的實現。 ## C++ ``` // C++ program to calculate the maximum // absolute difference of an array. #include <bits/stdc++.h> using namespace std; // Function to return maximum absolue // difference in linear time. int maxDistance(int arr[], int n) { ????// max and min variables as described ????// in algorithm. ????int max1 = INT_MIN, min1 = INT_MAX; ????int max2 = INT_MIN, min2 = INT_MAX; ????for (int i = 0; i < n; i++) { ????????// Updating max and min variables ????????// as described in algorithm. ????????max1 = max(max1, arr[i] + i); ????????min1 = min(min1, arr[i] + i); ????????max2 = max(max2, arr[i] - i); ????????min2 = min(min2, arr[i] - i); ????} ????// Calculating maximum absolute difference. ????return max(max1 - min1, max2 - min2); } // Driver program to test the above function. int main() { ????int arr[] = { -70, -64, -6, -56, 64, ??????????????????61, -57, 16, 48, -98 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << maxDistance(arr, n) << endl; ????return 0; } ```