# 值和索引和的最大绝对差 > 原文： [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; } ```