ค้นหาคู่ที่มีผลรวมสูงสุดในเมทริกซ์โดยใช้ C++

ในบทความนี้ เราจะพูดถึงการหาคู่ที่มีผลรวมสูงสุดในเมทริกซ์ที่กำหนดหรืออาร์เรย์ 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.

แนวทางในการหาทางออก

มาดูคำอธิบายสั้น ๆ เกี่ยวกับขั้นตอนต่าง ๆ เพื่อแก้ปัญหาที่กำหนดโดยไม่มีปัญหาใด ๆ

แนวทางกำลังเดรัจฉาน

ใช้วิธี Brute-force ได้ กล่าวคือ เริ่มต้นตัวแปร MAX ด้วยผลรวมของสององค์ประกอบแรก จากนั้นข้ามผ่านอาร์เรย์และการตรวจสอบของทุกคู่ หากมีค่ามากกว่า MAX MAX ของค่าผลรวมใหม่ แต่กระบวนการนี้จะใช้เวลามากขึ้นด้วยความซับซ้อนของเวลาของ O((m*n)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 มิติและการเริ่มต้น MAX1 และ MAX2 ด้วยค่าต่ำสุดของ INT
• การข้ามผ่านเมทริกซ์
  • หากส่วนปัจจุบันสำคัญกว่า MAX1 ให้แทนที่ MAX2 ด้วย MAX1 และ MAX1 ด้วยองค์ประกอบปัจจุบัน
  • หากชิ้นส่วนปัจจุบันมีขนาดเล็กกว่า MAX1 และมีความหมายมากกว่า MAX2 ให้แทนที่ MAX2 ด้วยองค์ประกอบปัจจุบัน
• คำนวณผลลัพธ์โดยบวก MAX1 และ MAX2 สองตัวแล้วพิมพ์งาน

บทสรุป

ในบทความนี้ เราได้พูดถึงการหาคู่ที่มีผลรวมสูงสุดในเมทริกซ์ที่กำหนด เราได้พูดคุยถึงแนวทางในการค้นหาวิธีแก้ปัญหาและยังได้กล่าวถึงโค้ด C++ ในลักษณะเดียวกัน เราสามารถเขียนโค้ดนี้ในภาษาอื่นๆ เช่น Java, C, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์