मान लीजिए 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
