Trong bài viết này, chúng ta sẽ thảo luận về việc tìm một cặp có tổng lớn nhất trong một ma trận hoặc mảng 2-D cho trước. Ví dụ
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. Phương pháp tiếp cận để tìm ra giải pháp
Hãy giải thích ngắn gọn về các quy trình khác nhau để giải quyết vấn đề đã cho mà không gặp bất kỳ vấn đề nào.
Phương pháp tiếp cận bạo lực
Có thể áp dụng cách tiếp cận Brute-force, tức là khởi tạo biến MAX bằng tổng của hai phần tử đầu tiên và sau đó duyệt qua mảng và tổng kiểm tra của mọi cặp nếu nó có giá trị lớn hơn MAX MAX giá trị tổng mới. Nhưng quá trình này sẽ mất nhiều thời gian hơn với độ phức tạp về thời gian là O ((m * n) 2).
Phương pháp tiếp cận hiệu quả
Có thể áp dụng một cách tiếp cận hiệu quả, tức là khởi tạo hai biến MAX1 và MAX2 bằng 0 và sau đó duyệt qua mảng 2-D; kiểm tra xem phần tử hiện tại có quan trọng hơn MAX1 hay không. Nếu có, hãy thay MAX2 bằng MAX1 và MAX1 bằng phần hiện có. Bằng cách này, chúng ta có thể tìm được hai số lớn nhất và hiển nhiên, tổng của hai số nguyên sẽ là số lớn nhất.
Ví dụ
#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;
} Đầu ra
maximum sum in Matrix : 107
Giải thích về đoạn mã trên
- Lưu trữ các phần tử trong mảng 2-D và khởi tạo MAX1 và MAX2 với giá trị nhỏ nhất là INT.
- Duyệt qua ma trận.
- Nếu phần hiện tại quan trọng hơn MAX1, thì hãy thay MAX2 bằng MAX1 và MAX1 bằng phần tử hiện tại.
- Nếu phần hiện tại nhỏ hơn MAX1 và có ý nghĩa hơn MAX2, thì hãy thay MAX2 bằng phần tử hiện tại.
- Tính toán kết quả bằng cách cộng hai MAX1 và MAX2 và in tác phẩm.
Kết luận
Trong bài viết này, chúng ta đã thảo luận về việc tìm một cặp có tổng lớn nhất trong một ma trận cho trước. Chúng tôi đã thảo luận về cách tiếp cận tìm giải pháp và cũng thảo luận về mã C ++ cho tương tự. Chúng tôi có thể viết mã này bằng bất kỳ ngôn ngữ nào khác như Java, C, Python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.