C++로 작성된 행렬에서 최대 합을 갖는 쌍을 찾는 알고리즘

이 기사에서는 주어진 행렬이나 2D 배열에서 최대 합을 갖는 쌍을 찾는 방법에 대해 설명합니다. 예를 들어

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으로 두 세트 초기화한 다음 2차원 배열을 순회하여 현재 요소가 MAX1보다 더 중요한지 확인합니다. 그렇다면 MAX2를 MAX1로, MAX1을 기존 부품으로 교체하세요. 이런 식으로 우리는 두 개의 가장 큰 숫자를 찾을 수 있습니다. 분명히 두 정수의 합이 가장 큽니다.

Example

#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;
}

Output

maximum sum in Matrix : 107

위 코드 설명

• 은 요소를 2차원 배열로 저장하고 MAX1과 MAX2를 최소값 INT로 초기화합니다.
• 행렬을 횡단하세요.
  • MAX1보다 현재 부분이 더 중요하다면 MAX2를 MAX1로, MAX1을 현재 요소로 바꾸세요.
  • 현재 부분이 MAX1보다 얇고 MAX2보다 의미가 있다면 MAX2를 현재 요소로 교체하세요.
• 두 개의 MAX1과 MAX2를 더하여 결과를 계산하고 결과를 인쇄합니다.

>

결론

이 기사에서는 주어진 행렬에서 최대 합을 갖는 쌍을 찾는 방법에 대해 논의했습니다. 우리는 해결책을 찾는 방법에 대해 논의하고 동일한 C++ 코드에 대해서도 논의했습니다. 이 코드는 Java, C, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++로 작성된 행렬에서 최대 합을 갖는 쌍을 찾는 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!