資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時裝研究
法律研究用 C++ 查詢矩陣中的特定對
假設有一個 n x n 整數矩陣 mat。我們需要找到所有索引選擇中最大的 mat(c, d) - mat(a, b) 值。這裡我們必須記住 c > a 且 d > b。因此，如果矩陣如下所示 −
| 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 |
輸出將為 18。這是因為 mat[4, 2] - mat[1, 0] = 18 差異最大。
為了解決這個問題，我們將預處理矩陣，使索引 (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
更新於：2020 年 1 月 3 日
276 次觀看
廣告