หาแถวที่มีผลรวมมากที่สุดในเมทริกซ์ใน C++

ในปัญหานี้ เราได้รับเมทริกซ์ mat[][] ขนาด N*N งานของเราคือ หาแถวที่มีผลรวมมากที่สุดในเมทริกซ์

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

mat[][] = { 
    8, 4, 1, 9 
    3, 5, 7, 9 
    2, 4, 6, 8 
    1, 2, 3, 4 
}

Output

Row 2, sum 24

อธิบาย

Row 1: sum = 8+4+1+9 = 22 
Row 2: sum = 3+5+7+9 = 24 
Row 3: sum = 2+4+6+8 = 20 
Row 4: sum = 1+2+3+4 = 10

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

วิธีแก้ที่ง่ายคือหาผลรวมขององค์ประกอบแต่ละแถว และติดตามผลรวมสูงสุด แล้วหลังจากทะลุแถวทั้งหมด ให้คืนค่าแถวที่มีผลรวมสูงสุด

โปรแกรมแสดงการทำงานของวิธีแก้

ตัวอย่าง

#include <iostream> 
using namespace std; 
#define R 4 
#define C 4 

void findMax1Row(int mat[R][C]) { 
    int maxSumRow = 0, maxSum = -1; 
    int i, index; 
    for (i = 0; i < R; i++) { 
        int sum = 0; 
        for(int j = 0; j < C; j++){ 
            sum += mat[i][j]; 
        } 
        if(sum > maxSum){ 
            maxSum = sum; 
            maxSumRow = i; 
        } 
    } 
    cout<<"Row: "<<(maxSumRow+1)<<" has the maximum sum which is "<<maxSum; 
} 

int main() { 
    int mat[R][C] = { 
        {8, 4, 1, 9}, 
        {3, 5, 7, 9}, 
        {2, 4, 6, 8}, 
        {1, 2, 3, 4} 
    }; 
    findMax1Row(mat); 
    return 0; 
}

ผลลัพธ์

Row: 2 has the maximum sum which is 24