在本文中,我们将讨论在给定矩阵或二维数组中找到具有最大和的对。例如
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)。
可以应用一种有效的方法,即用 0 初始化两变量 MAX1 和 MAX2,然后遍历二维数组;检查当前元素是否比 MAX1 更重要。如果是,则将 MAX2 替换为 MAX1,将 MAX1 替换为现有部件。这样,我们就能找到两个最大数了,显然,两个整数之和最大。
#include <bits/stdc++.h> using namespace std; int main() { int m = 3, n = 3; // 用值初始化矩阵 int matrix[m][n] = { { 55, 22, 46 }, { 6, 2, 1 }, { 3, 24, 52 } }; // 初始化 MAX1 和 MAX2 以保持两个最大数字。 int MAX1 = INT_MIN; int MAX2 = INT_MIN; int result; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 检查元素是否大于 MAX1。 if (matrix[i][j] > MAX1) { MAX2 = MAX1; MAX1 = matrix[i][j]; } // 检查当前元素是否在 MAX1 和 MAX2 之间。 else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) { MAX2 = matrix[i][j]; } } } // 通过将两个最大数字相加来计算最大总和。 result = MAX1 + MAX2; cout << "矩阵中的最大和: " << result ; return 0; }输出结果
矩阵中的最大和: 107
在二维数组中存储元素并用最小值 INT 初始化 MAX1 和 MAX2。
遍历矩阵。
如果电流部分比 MAX1 更重要,则将 MAX2 替换为 MAX1,将 MAX1 替换为电流元素。
如果当前片段比 MAX1 更精简且比 MAX2 更有意义,则将 MAX2 替换为当前元素。
通过将两个 MAX1 和 MAX2 相加计算结果并打印工作。
在本文中,我们讨论了在给定矩阵中找到具有最大和的对。我们讨论了寻找解决方案的方法,还讨论了相同的 C++ 代码。我们可以使用任何其他语言(如 Java、C、Python 等)编写此代码。我们希望本文对您有所帮助。