在C ++中的Matrix中查找特定对
假设有一个nxn的整数矩阵。我们必须在所有索引选择上找到mat(c,d)-mat(a,b)的最大值。在这里，我们必须记住c>a和d>b。所以如果矩阵像-
输出为18。这是因为mat[4，2]-mat[1，0]=18具有最大差异。
为了解决这个问题，我们将对矩阵进行预处理，以使index(i,j)将矩阵中从(i,j)到(n-1,n-1)的元素的最大值存储起来，在此过程中，将继续更新到目前为止找到的最大值。然后，我们将返回最大值。
示例
#include<iostream>
#define N 5
using namespace std;
int findMaxValue(int matrix[][N]) {
int maxValue = -99999;
int arr_max[N][N];
arr_max[N-1][N-1] = matrix[N-1][N-1];
int max_val = matrix[N-1][N-1];
for (int j = N - 2; j >= 0; j--) {
if (matrix[N-1][j] > max_val)
max_val = matrix[N - 1][j];
arr_max[N-1][j] = max_val;
}
max_val = matrix[N - 1][N - 1];
for (int i = N - 2; i >= 0; i--) {
if (matrix[i][N - 1] > max_val)
max_val = matrix[i][N - 1];
arr_max[i][N - 1] = max_val;
}
for (int i = N-2; i >= 0; i--) {
for (int j = N-2; j >= 0; j--) {
if (arr_max[i+1][j+1] - matrix[i][j] > maxValue)
maxValue = arr_max[i + 1][j + 1] - matrix[i][j];
arr_max[i][j] = max(matrix[i][j],max(arr_max[i][j + 1],arr_max[i + 1][j]) );
}
}
return maxValue;
}
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);
}输出结果
Maximum Value is 18