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

ในบทความนี้ เราจะอภิปรายการหาคู่ที่มีผลรวมสูงสุดในเมทริกซ์หรืออาร์เรย์ 2 มิติที่กำหนด ตัวอย่างเช่น:

Input : matrix[m][n] = {   { 3, 5, 2 },   { 2, 6, 47 },   { 1, 64, 66 } }
Output : 130
คำอธิบาย : ผลรวมสูงสุดคือ 130 จากคู่องค์ประกอบ 64 และ 66

Input : matrix[m][n] = {   { 55, 22, 46 },   { 6, 2, 1 },   { 3, 24, 52 } }
Output : 107
คำอธิบาย : ผลรวมสูงสุดคือ 107 จากคู่องค์ประกอบ 55 และ 52

วิธีการแก้ปัญหา

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

วิธี Brute-force

วิธี Brute-force สามารถนำมาใช้ได้ คือ เริ่มต้นตัวแปร MAX ด้วยผลรวมของสององค์ประกอบแรก แล้วเดินทางผ่านอาร์เรย์และตรวจสอบผลรวมของทุกคู่ หากมากกว่า MAX ให้ MAX เป็นค่าผลรวมใหม่ แต่กระบวนการนี้จะใช้เวลามากด้วยความซับซ้อนด้านเวลา O((m×n)²)

วิธีที่มีประสิทธิภาพ (Efficient Approach)

วิธีที่มีประสิทธิภาพสามารถนำมาใช้ได้ คือ เริ่มต้นตัวแปรสองตัว MAX1 และ MAX2 ด้วย 0 แล้วเดินทางผ่านอาร์เรย์ 2 มิติ ตรวจสอบว่าองค์ประกอบปัจจุบันมากกว่า 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 << "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 ฯลฯ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์