在本文中,我们将讨论在给定矩阵或二维数组中查找具有最大和的对。例如
'Input : matrix[m][n] = {
{ 3, 5, 2 },
{ 2, 6, 47 },
{ 1, 64, 66 } }
Output : 130
Explanation : maximum sum is 130 from element pair 64 and 66.
Input : matrix[m][n] = {
{ 55, 22, 46 },
{ 6, 2, 1 },
{ 3, 24, 52 } }
Output : 107
Explanation : maximum sum is 130 from element pair 55 and 52.
寻找解决方案的方法
让我们简要说明一下解决给定问题而不出现任何问题的不同过程。
暴力方法
可以应用暴力方法,即用前两个元素的和初始化 MAX 变量,然后遍历数组并检查每对元素的校验和(如果它比 MAX 更重要) MAX 为新的和值。但这个过程会花费更多的时间,时间复杂度为O((m*n)2)。高效的方法
可以采用一种高效的方法,即初始化两个-将变量 MAX1 和 MAX2 置为 0,然后遍历二维数组;检查当前元素是否比 MAX1 更重要。如果是,则用 MAX1 替换 MAX2,用现有部件替换 MAX1。这样,我们就能找到两个最大的数,显然,两个整数之和就是最大的。
示例
'#include <bits/stdc++.h>
using namespace std;
int main() {
int m = 3, n = 3;
// initialising matrix with values
int matrix[m][n] = {
{ 55, 22, 46 },
{ 6, 2, 1 },
{ 3, 24, 52 }
};
// initialising MAX1 and MAX2 to keep two maximum numbers.
int MAX1 = INT_MIN;
int MAX2 = INT_MIN;
int result;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// check if the element is greater than MAX1.
if (matrix[i][j] > MAX1) {
MAX2 = MAX1;
MAX1 = matrix[i][j];
}
// check if the current element is between MAX1 and MAX2.
else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) {
MAX2 = matrix[i][j];
}
}
}
// calculating maximum sum by adding both maximum numbers.
result = MAX1 + MAX2;
cout << "maximum sum in Matrix : " << result ;
return 0;
}
输出
'maximum sum in Matrix : 107
上述代码说明
- 在二维数组中存储元素,并用最小值 INT 初始化 MAX1 和 MAX2。
- 遍历矩阵。
- 如果当前部分比 MAX1 更重要,则用 MAX1 替换 MAX2,用当前元素替换 MAX1。
- 如果当前部分是比 MAX1 更精简,比 MAX2 更有意义,然后用当前元素替换 MAX2。
- 通过将两个 MAX1 和 MAX2 相加计算结果并打印结果。
结论
在本文中,我们讨论了在给定矩阵中寻找具有最大和的对。我们讨论了寻找解决方案的方法,也讨论了同样的 C++ 代码。我们可以用任何其他语言(例如 Java、C、Python 等)编写此代码。我们希望本文对您有所帮助。