# 在矩阵中查找特定对 > 原文： [https://www.geeksforgeeks.org/find-a-specific-pair-in-matrix/](https://www.geeksforgeeks.org/find-a-specific-pair-in-matrix/) 给定一个整数的 nxn 矩阵 mat [n] [n]，求出所有索引选择的 mat（c，d）– mat（a，b）的最大值，以使 c > a 和 d > b。 **示例**： ``` Input: mat[N][N] = {{ 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 }, { 3, 8, 6, 1, 3 }, { -4, -1, 1, 7, -6 }, { 0, -4, 10, -5, 1 }}; Output: 18 The maximum value is 18 as mat[4][2] - mat[1][0] = 18 has maximum difference. ``` 该程序应只对矩阵进行一次遍历。 即预期时间复杂度为 `O(n^2)` 一种简单的**解决方案**是应用暴力。 对于矩阵中的所有值 mat（a，b），我们找到具有最大值的 mat（c，d），使得 c > a 和 d > b 并继续更新到目前为止找到的最大值。 我们最终返回最大值。 以下是其实现。 ## C++ ```cpp // A Naive method to find maximum value of mat[d][e] // - ma[a][b] such that d > a and e > b #include <bits/stdc++.h> using namespace std; #define N 5 // The function returns maximum value A(d,e) - A(a,b) // over all choices of indexes such that both d > a // and e > b. int findMaxValue(int mat[][N]) {     // stores maximum value     int maxValue = INT_MIN;     // Consider all possible pairs mat[a][b] and     // mat[d][e]     for (int a = 0; a < N - 1; a++)     for (int b = 0; b < N - 1; b++)         for (int d = a + 1; d < N; d++)         for (int e = b + 1; e < N; e++)             if (maxValue < (mat[d][e] - mat[a][b]))                 maxValue = mat[d][e] - mat[a][b];     return maxValue; } // Driver program to test above function int main() { int mat[N][N] = {                 { 1, 2, -1, -4, -20 },                 { -8, -3, 4, 2, 1 },                 { 3, 8, 6, 1, 3 },                 { -4, -1, 1, 7, -6 },                 { 0, -4, 10, -5, 1 }             };     cout << "Maximum Value is "         << findMaxValue(mat);     return 0; } ```