একটি n x n ম্যাট্রিক্স দেওয়া আছে। 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 |
সর্বোচ্চ পার্থক্য ১৮ (mat[4][2] - mat[1][0] = 10 - (-8) = 18)।
একটি arr_max ম্যাট্রিক্স তৈরি করুন যেখানে arr_max[i][j] = (i,j) থেকে (n-1,n-1) পর্যন্ত সর্বোচ্চ মান। এরপর arr_max[i+1][j+1] - matrix[i][j] এর সর্বোচ্চ মান বের করুন।
#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
