이 기사에서는 주어진 행렬 또는 2차원 배열에서 최대 합을 갖는 쌍을 찾는 것에 대해 논의할 것입니다. 예를 들어
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)의 시간 복잡도로 인해 더 많은 시간이 소요됩니다.
효율적인 접근
효율적인 접근 방식을 적용할 수 있습니다. 즉, 2변수 MAX1 및 MAX2를 0으로 초기화한 다음 2차원 어레이를 통과합니다. 현재 요소가 MAX1보다 더 중요한지 확인하십시오. 그렇다면 MAX2를 MAX1로, 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
위 코드 설명
- 2차원 배열에 요소를 저장하고 INT의 최소값으로 MAX1 및 MAX2를 초기화합니다.
- 행렬 순회.
- 현재 부분이 MAX1보다 더 중요한 경우 MAX2를 MAX1로, MAX1을 현재 요소로 교체합니다.
- 현재 조각이 MAX1보다 축소되고 MAX2보다 더 의미가 있는 경우 MAX2를 현재 요소로 교체합니다.
- MAX1과 MAX2 두 개를 더하여 결과를 계산하고 작업을 인쇄합니다.
결론
이 기사에서 우리는 주어진 행렬에서 최대 합을 갖는 쌍을 찾는 것에 대해 논의했습니다. 우리는 솔루션을 찾는 접근 방식에 대해 논의했으며 동일한 솔루션에 대한 C++ 코드도 논의했습니다. 이 코드는 Java, C, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 문서가 도움이 되기를 바랍니다.