# 與給定的總和和距末端的最大最短距離配對 > 原文： [https://www.geeksforgeeks.org/print-maximum-shortest-distance/](https://www.geeksforgeeks.org/print-maximum-shortest-distance/) 給定一個由 N 個整數和一個整數 K 組成的數組，請選擇兩個總和為 K 的不同元素，并找出所選擇元素到端點的最大最短距離。 **示例**： ``` Input : a[] = {2, 4, 3, 2, 1} k = 5. Output : 2 Explanation: Select the pair(4, 1). Shortest distance of 4 from ends = 2 Shortest distance of 1 from ends = 1 Hence, answer is max(2, 1) = 2 Input : a[] = {2, 4, 1, 9, 5} k = 3 Output : 3 Explanation: Select the pair (2, 1) Shortest distance of 2 from ends = 1 Shortest distance of 1 from ends = 3 Hence, answer is max(1, 3) = 3\. ``` **注意**：末端元素到末端的距離是 1 而不是 0。 **樸素的方法**：該方法是運行兩個循環，并在內部循環中檢查兩個元素是否與和 k 成對。 如果是，則以兩個元素之間最短距離的最大值作為答案，將其與前一對元素的最短距離進行比較，并以這兩個元素中的最小值作為答案。 循環結束時，我們將獲得所需的輸出。 **有效方法**：顯然，最短距離是指距左端的距離和距右端的距離，即。 讓我們將第 i 個元素的最短距離表示為。 還有另一種情況，即重復選定對中的一個元素，然后在該元素出現的所有最短距離中選擇最小的一個。 循環運行，并將所有數組元素中最短的距離存儲在另一個數組中（將其設為![D[]](https://img.kancloud.cn/d4/27/d427ad9a37b51a2602818e0b7e5f8d3d_34x28.png "Rendered by QuickLaTeX.com")）。 現在，我們得到了所有元素的最短距離。 運行 for 循環。 如果選取的元素是 **x** ，則另一個元素應該是 **k-x** 。 用![max(D[x], D[k-x])](https://img.kancloud.cn/a4/6a/a46a34e1bb2234f5a78ec7ba46cc1afb_233x28.png "Rendered by QuickLaTeX.com")更新 ans，并在每次更新時，選擇先前和當前答案中的最小值。 如果 **k-x** 不在數組中，則![D[k-x]](https://img.kancloud.cn/aa/bc/aabcbd7b0b09d2fd0f3100145f893064_96x28.png "Rendered by QuickLaTeX.com")將為 INFINITE，這將已經初始化。 ## C++ ```cpp // C++ code to find maximum shortest distance? // from endpoints #include <bits/stdc++.h> using namespace std; // function to find maximum shortest distance int find_maximum(int a[], int n, int k) {??? ????// stores the shortest distance of every? ????// element in original array. ????unordered_map<int, int> b; ????for (int i = 0; i < n; i++) { ????????int x = a[i]; ????????// shortest distance from ends ????????int d = min(1 + i, n - i);? ????????if (b.find(x) == b.end()) ????????????b[x] = d;?? ????????else ????????????/* if duplicates are found, b[x]? ????????????is replaced with minimum of the ????????????previous and current position's ????????????shortest distance*/ ????????????b[x] = min(d, b[x]);? ????} ????int ans = INT_MAX; ????for (int i = 0; i < n; i++) { ????????int x = a[i]; ????????// similar elements ignore them? ????????// cause we need distinct elements???? ????????if (x != k - x && b.find(k - x) != b.end())????????? ????????????ans = min(max(b[x], b[k - x]), ans);???????? ????} ????return ans; } // driver code int main() { ????int a[] = { 3, 5, 8, 6, 7 }; ????int K = 11; ????int n = sizeof(a) / sizeof(a[0]); ????cout << find_maximum(a, n, K) << endl; ????return 0; } ```